<p>What is the best way (performance wise) to paginate results in SQL Server 2000, 2005, 2008, 2012 if you also want to get the total number of results (before paginating)?</p>

You didn't specify the language nor which driver you are using. Therefore I'm describing it abstractly.
Create a scrollable resultset / dataset. This required a primary on the table(s)
jump to the end
request the row count
jump to the start of the page
scroll through the rows until the end of the page