Нужно делать все, и Каталоги и Сапа и рекламные сети.
---
Прогон по каталогам делать полюбому полезно, наилучший ресурс - http://1ps.ru если лень самому возиться, бери самый дорогой тариф (2400 р.) но зато они сами все делают за тебя и (большой плюс), делают профессиональную анкету сайта, с ключевыми словами, описаниями и др, что тебе потом очень пригодится.
---
От Сапы слишком много переходов не жди, если только не покупаешь ссылки на "морде" мажорных сайтов (это стоит дорого). Но зато, со временем можно добиться повышения пузомерок.
---
Рекламная сеть - это самый прямой способ, особенно если контекстная реклама (целевая), но и стоит правда немало.
Для нормальной раскрутки, бюджет должен быть не менее $50 в месяц первые полгода.