While all these answers are saying to create a 16x16 icon, the reality is you should be creating both a 16x16 and 32x32, in order to support retina displays. None of the online generators did a very good job with this.
On Mac, there is a great $5 app called Icon Slate, which allows you to easily create both formats in a single ICO file.
On Windows, I've used Axialis IconWorkshop with great success, but it's a much heavier-duty tool, and is significantly more expensive at about €50.
Both will create an ico file with both 16x16 and 32x32 images within it.
If you're using the asset pipeline, use the app/assets/images folder rather than /public. The number of fringe browsers that ignore the link
tag is rapidly approaching zero, so jumping through hoops to accommodate them isn't worth it.
As mentioned in other answers, use this in the head
to display it:
<%= favicon_link_tag 'favicon.ico' %>