Top or bottom:
A user is unlikely to need to know whether they need to move to another page until they've reached the bottom of the current page. So at a minimum place the page navigation at the bottom. That's assuming we are looking at results sorted by relevance rather than by some un-prioritized ordering.
Left or right
Position at bottom right for L-R languages. Right meaning right-aligned with the right hand edge of the result block itself - not to the frame of the page.
Optionally if your pagination was reduced to previous / next or newer / older for example (so not really pagination at all!) then you may split backward links to the left and forward links to the right (like TechCrunch for example).
Top and bottom?
If not all the results can be (made to be) guaranteed to fit on one page, then you might be tempted to also add them at the top so they are always visible.
Why then, does Google, in its infinite wisdom, not place navigation at top as well as bottom, (which they did actually used to do)?
By placing navigation at the top you may be prioritizing the navigation over the results themselves and offering a possible route to the next page without exploring the results below the fold, meaning that results at top of page n+1 may have more visibility than the results at the bottom of page n.
For this reason, try to avoid positioning them at the top - besides it may allow for an extra result to be displayed on the page. If this means detecting a suitable number of results to fit above the fold then that may be something worth testing.
Users like to be able to click successively to the next page without moving the mouse, so even if all your results fit on one unscrolled page, but you cannot guarantee the position of the bottom navigation to be the same on each page, then you may have a viable reason to position the navigation at the top where you can be sure of a constant positioning. Personally in this case, I would prefer a small gap and constant position than no gap and a varying position.
If your results are in fact not ordered by relevance then you may well need to put the navigation at the top anyway because it should essentially become part of your search terms (a form of indexing system) rather than being purely a pagination of results.
Finally - do you need it at all?
Consider whether an auto-load-on-scroll 'infinite' scrolling list may fit the purpose better than pagination. More and more examples of this are appearing, but it does very much depend on your particular scenario, for example a requirement for a sense of actual location within results or the need to be able to easily flip back and forth to specific page results and such like.
Quince Infragistics Paging Patterns
Wellie Paging pattern
UI-patterns Paging pattern
Total Usability pagination controls
ux.se question: Whats the design rationale behind putting the pagination of the bottom end of the search results?
Note: I can't find what I consider to be an important missing reference as to google's own reasoning for removing pagination from the top of the results - I can't even remember how long ago that was.