From StrategyWiki, the free strategy guide and walkthrough wiki

Mail is the cheapest item in the game at 50. It lets you give the reciever on the end of a trade a short message. A neat item, but if you don't trade it's kind of worthless.

Name	Design	Location
Air Mail	Red, blue and white borders with a white background.	Jubilife City Pokémart
Bloom Mail	Purple and Pink Flowers with a pink background.	Floaroma Town Pokémart
Bubble Mail	Small bubbles with a blue background.	Veilstone Department Store
Flame Mail	Yellow fire with a red background.	Veilstone Department Store
Grass Mail	Grassy borders that gets lighter colored in the middle.	Veilstone Department Store
Heart Mail	A big heart in the middle with a pink background.	Hearthome City Pokémart
Snow Mail	Icicles and a blizzard, has a light blue background.	Snowpoint City Pokémart
Space Mail	A purple galaxy with a dark purple background.	Veilstone Department Store
Steel Mail	Grey with borders around the message.	Sunyshore City Pokémart
Tunnel Mail	Light brown spikey borders with a brown background.	Oreburgh City Pokémart