Wow. Where to start
You could go down the free advertising route and do things like register on mobile phone related forums and place your website address in your signature there and also if these forums have Marketplace sections like namepros.com does, then you could advertise in there.
You could also use technorati.com to find mobile phone related blogs and post interesting comments on those blogs with your website address there aswell.
You could then of course spend a bit of money on text links using google adwords and adbrite and target sites related to your product.
Theres so much you could do, and i think the best thing you could do is spend few hours reading through marketing forums and get more tips through specialized sites like that.
-- Phil