I don’t really have a budget to spend on advertising my app to attract users. Is there anything I can do on-Facebook?
Work the integration points like there’s no tomorrow. See Facebook Platform Integration Points for more information about the different points and how best to use them.
Spreading through the social graph is still the most powerful mechanism for attracting users because those users tend to be much higher-value (they are drawn to your app because their friends use it, rather than because they come across it in an ad). Experiment aggressively during the early days of your app to figure out what works as content in invitations, requests, message attachments, etc., and then make sure you don’t get lazy and allow competitors to bypass you on any one of the points. As with the different ad networks, make sure you’re measuring your success at the different points so that you can quickly adjust if things aren’t panning out (see Measuring Your Success).