Is that route declared above any RESTful resources routes? That is, your route file should look like the following:

map.connnect  /products/page/:page , :controller =>  products , :action =>  index 
map.resources :products, :except => [:index]

If your routes look correct, you could try monkey-patching the way will_paginate generates the page links. It does so in WillPaginate::ViewHelpers#url_for(page). It s some fairly complex logic in order to handle some tricky edge cases, but you could write a new version that tried the simple version for your products first:

# in lib/cache_paginated_projects.rb
WillPaginate::ViewHelpers.class_eval do
  old_url_for = method(:url_for)
  define_method(:url_for) do |page|
    if @template.params[:controller].to_s ==  products  && @template.params[:action].to_s ==  index 
      @template.url_for :page => page
    else
      old_url_for.bind(self).call(page)
    end
  end
end

this works for me

app/helpers/custom_link_renderer.rb

class CustomLinkRenderer < WillPaginate::LinkRenderer
  def page_link(page, text, attributes = {})
    @template.link_to text, "#{@template.url_for(@url_params)}/page/#{page}", attributes
  end
end

add this line to config/environment.rb file

WillPaginate::ViewHelpers.pagination_options[:renderer] =  CustomLinkRenderer 

A little addition to the current answers, I had to spend hours to figure it out.

If you have some more complex routes, like for example including filtering in my case, make sure that the "higher level" routes come first (and not just that they are above the RESTful one), otherwise will_paginate picks up the first usable one and sticks the extra params at the end of the URL in a non-pretty way.

So in my case I ended up with this:

map.connect "wallpapers/:filter/page/:page", :controller => "wallpapers", :action => "index", :requirements => {:page => /d+/, :filter => /(popular|featured)/ }
map.connect "wallpapers/page/:page", :controller => "wallpapers", :action => "index", :requirements => {:page => /d+/ }
map.resources :wallpapers

So now I get pretty URLs like: wallpapers/popular/page/2 instead of wallpapers/page/2?filter=popular

Do this:

map.products_with_pages "/products/page/:page", :controller => "products", :action => "index"

You can even do it with a has_many ie: products has_many :items

map.resources :products do |product|
  map.items_with_pages "/products/:id/page/:page", :controller => "products", :action => "show"
end

Then your controller could look like

def show
  product = Product.find(params[:id])
  @items = product.items.paginate :per_page => 5, :page => params[:page]
end

Which would give you a url like: http://domain.com/products/123/page/3 where 123 is the product id and 3 is the page id. You could also use permalinks and have the 123 id changed to a more seo friendly word.