Aside from a few quests and a repeatable turn-in that culminates this process, the Love is in the Air gifts and pledges are all obtained in a similar fashion. You get , , , and from NPCs in the three participating cities of your faction (the capital cities prior to The Burning Crusade). Guards give "Pledges of" and non-guards give "Gifts of".
If you do not have the Adored debuff, you get the "of Adoration" item and the adored debuff for one hour (of real time, not game time), then for that hour you can only get the "of Friendship" item. Both gifts contain a pledge item (see Creates section below), but the Gift of Adoration contains a functional gift as well. Think of the "of Friendship" item as a farmable consolation prize you can collect between the availability of the real gifts. All of the "of Adoration" gifts, from guards and non-guards, from any city, from either faction, contain the same random functional items, but the pledge items are unique, so each city's NPCs (by race) give a specific set of container items that contain the NPC type specific and city specific pledge item. An NPC of a race associated with another city gives the gifts of that other city.
The NPC must have a heart floating over their head, and few of the non-guard NPCs have the heart. You will only be able to give the Love Tokens to NPCs if you are wearing for female NPCs or for male NPCs, and you will only be able to see the hearts if you are wearing either. The hearts have a 1-2 minute cooldown after anyone gives the NPC a Love Token and receives a gift.
You will not always get a gift, sometimes you will receive a Heartbroken debuff instead. This debuff lasts an hour and prevents you from using Love Tokens, but can be removed by another player using an on you. You must have an open slot in your inventory or a stack of less than 100 in your inventory to have an Unbestowed Friendship Bracelet successfully used on you, creating a Friendship Bracelet and removing the Heartbroken debuff. As of Love is in the Air 2009, there is an achievement to use Unbestowed Friendship Bracelets on players (requires them to have the Heartbroken debuff), so if you get the debuff, it is not terribly difficult to find someone willing to remove it, even in the wee hours of the morning.
Only the NPCs with the city's guard name count as guards. Vendor NPCs are non-guards, but also named NPCs with guard duties; basically anyone who isn't a generic guard. The innkeepers have the floating heart but do not count as non-guard NPCs for the event; they do not give gifts, rather, they are the source for the items you need to farm the gifts, the cologne, perfume and Love Tokens, (and their heart is always visible, not requiring that you be wearing cologne or perfume).
You must have an open slot in your inventory to receive a Gift of Friendship. The item does not stack. If you attempt to obtain one without an empty slot, your Love Token is consumed, the NPC's floating heart goes on cooldown, you run the risk of the Heartbroken debuff; you just don't get the item.