I think I'd start with advertising on various bitcoin related forums, and maybe in some of the IRC channels on freenode (If it is in compliance with the rules).
I don't know how hard/easy it is to get your business listed on https://en.bitcoin.it/wiki/Trade
, but you should do that too if possible. I suppose they will make more elaborate categories as more businesses are added to the list.
As bitcoins become more mainstream it will also get easier to advertise in more mainstream medias i guess..
Stuff like this is exactly what we need to strengthen the bitcoin economy. More markets => more exposure => even more markets.