On my Opportunity object I have a look up to Primary Contact. I would to enable users to create a New contact when using the lookup. I would like to have a 'New' Button next to 'Search' search layout. I cannot see where this is possible. Any ideas?
I believe you're asking to add a new button to the actual lookup window.
The only way (without writing code) is to enable the Quick Create function in
Setup > Customize > User Interface > Enable Quick Create
There are some big problems with that feature however - doesn't enforce validation rules, can't edit the form, can't control object by object (all or nothing).
Check out the excellent post by Jeff Douglas on a possible workaround.