Note that Google have implemented an age delay for new sites. No matter how many inbound links you get or no matter how well optimised your site is for the search engines, your site will not receive high placement with Google for 6-9 months from the time Google's bots' first spider it.
Best advice I can give (for Google) is to sign up with Google Sitemaps and register your site. After that, it's a matter of playing the horrible waiting game - don't torture yourself changing the layout of your site etc. as it won't make the least bit of difference...