Short answer: 16 x 16 pixels.
Long answer:
.ico files can actually contain multiple images, at multiple colour depths – you can provide 16×16, 32×32, 48×48 and 64×64 in a single file and the OS will pick the best one to show.
Of course to keep the file size low you don’t want to put too many in there, but if you think people might be saving a link on their desktop (say it’s a web application) then it’s probably a good move.