> 1. Should I do it on the client or the server?
I think most applications use both client and server components. If your question is more on the lines of which one plays a major role, it depends mostly on the app. GMail won't be half as good without all the JS magic, but again, I assume it also has a heavy server component.
> 2. What should be travelling between the client and the server?
If you need any client side processing or are using a framework which works on raw data(backbone.js), then json/xml/...; or else if your goal is to run the app without reloading unnecessary parts, html is a better idea.
> 3. Based on the answer to #2, what else do I need on the client?
I am not sure what you are looking for here, but if your goal is to make a responsive app, there are some basic things to take care of.
Have bookmarkable links and don't break the back button. Doing that is breaking the base paradigm, and plain ajax does that.
Use something that provides bookmarkable links, and doesn't break the back/forwrad button; and at the same time, doesn't reload the whole page when only a small portion of the page needs reloading.
pjax is one such solution - the 37signals guys investigated it, then went with their home grown solution, but I think pjax will work just fine for majority of use cases.
The trick to pjax is serving content without layout if it is a pjax reques; with layout otherwise. There is nothing you can't handroll, but 1) why would you want to? 2) pjax uses pushState to preserve links and back button behavior.
Here is the pjax code:
https://github.com/defunkt/jquery-pjax
And here is a gist in Flask/Python which shows conditionally including the layout:
https://gist.github.com/830fc28c680e77759b4b