Do have a google webmasters account?
If not you can learn more about
webmaster tools here.
Once you have a webmaster tools account you will need to submit your site url and a site map using the tools provided.
The time taken by google to index your sites content can take rather a long time, especially if you don't have many links back to your site.
The reason I mention that is because there is a temptation to try and fix something which isn't broken, in an attempt to speed up indexing etc.
EDIT: The other search engines also have similar tools for managing the way they index your site.
You will also need to add the verification codes or files to your site. There a number of extensions on the JED which allow you to manage several search engine auth. codes easily, gavick templates cater for the google key.
Here is another method of including information in the page header
EasyHeader it's very useful for adding verification codes or css style sheet and scripts etc.
Hope that helps,