RailsでGitHubが使っているようなpushStateを使うにはどうすればよいでしょうか？

GitHub自身はこの手法を「pjax」と呼び、jqueryプラグインを公開しています。このプラグインは「X-PJAX: true」といった情報をHTTPヘッダーに送付し、サーバーサイドの方ではこの情報を元に普通のリクエストとpjaxリクエスト用にレスポンスを返す必要があります。railsだとrack-pjaxがあります。

# gem 'pjax_rails'  
gem 'rack-pjax'

# /config/application.rb
module Store  
  class Application < Rails::Application   
    config.middleware.use Rack::Pjax  
    # Other config commands omitted  
  end  
end  

上の例はASCII Castから引用しました。

それ以外にも私の作った同僚のOliverがつくった「Davis.js」というライブラリーもあります。

pjax jqueryプラグインとの違いですが、pjaxはサーバサイドとのajax通信を行うための規約を提供しているのですが、Davisはあくまでクライアントサイドのルーティングに特化しています。

 var app = Davis(function () {
   this.get('/welcome/:name', function (req) {
     $('body').append('<h1>Hello there, ' + req.params['name'] + '!</h1>')
   })
 })

 $(document).ready(function () {
   // append a link to trigger the route
   $('body').append('<a href="/welcome/bob">Greet</a>');

   app.start();
 })

Sammy.jsとほぼそっくり(よってSammy Davis Jrの名字から由来）に見えますが、普通のURLがルートに指定されているのが特徴です。これによって普通にそのURLのページをブラウザから最初に読み込んだ際にはサーバーサイドにアクセスされますが、他のページからのリンクやフォームからのクリックイベントが発生した時は、Davis.jsがそのイベントを補足し、Javascriptでダイナミックな動きを追加したり、サーバサイドにアクセスせずにクライアントサイドにすでにあるデータを使ってページを表示したりできます。