Hi Mani - have you posted over in the
Developer Spotlight Forum?
I've been releasing a slew of apps recently and always make sure to post there. Other than that the options you've got are:
Twitter - setup a user specific to your app - fill in ALL the bio details, good pictures / etc. Post screenshots, likes to videos, etc. Find people that are talking about similar things on twitter - retweet them, reply to them, favorite them, etc.
App landing page - whilst the Windows Phone store gives a pretty good view of your app, you might want more control (inclusion of demo videos etc) - so make sure to build an app landing page - (there are loads and loads of providers - I've been using Rocketstart.me recently -
Cricket In My Pocket) - If your budget allows get a full .com domain and website.
Do Facebook as SuperNu suggested.
If you can afford it then buy some Google Adwords. If you can't then maybe try integrating a cross promotional advertising network - I won't bother listing any - there are HUNDREDS, and I don't know which are any good (not used any myself)
Build a press pack (press release, screenshots, promo graphics, demo videos) and submit it to review sites - here's one I built for an iOS app -
https://www.dropbox.com/sh/9qbc136qtoku7ij/7pYsph8-Ek/flash-in-my-pocket/ios - if you're not paying for your reviews then expect it to take some time to appear.
Beyond that - generally get the word out, find forums and invite knowledgeable people to try it out.
Good luck!