I've started a Worgen character and have mailed him a handful of useful bits and pieces (heirlooms and other low level gear). However I haven't been able to find a mailbox in the Gilneas area since I was Level 1 in Gilneas City. I've reached Stormglen Village and was wondering when am I next likely to see a mailbox?
There aren't any. You'll see your first mailboxes (and flight points) when you leave that zone. The reason will make sense when you finish the zone quests...
I don't know exactly when this was added (likely patch 4.0.6), but there is now a mailbox in the starting square in Gilnaes.
If you turn around, it should be just past (and to the right of) Gwen Armstead, who gives you the quest Salvage the Supplies.
I'm not sure if any others were added or not.
There IS a mailbox in Gilneas, near Duskhaven, just outside the Inn.
I found one. If you run back into the city, in the Merchant Square that was the starting area, the mailbox is still there. Depending at what point in your questing you do this, however, the city might have forsaken crawling in it. For me, I was at the quest where you rescue the miners when I decided I really hated the toon and wanted to send off my looms.
Up until you trigger the forsaken to swarm the city (which I think isn't until you're on the quest to retake it), you can run back into the Merchant Square and use the mailbox.