When restoring my system from a backup, I mysteriously lost the ability to navigate or create any form of tcsh history. To my surprise, I couldn't find an answer on Mac OS X Hints. The solution for me was quite simple: make sure all the dotfiles initializing the shell (such as .tcshrc or ~/Library/init/tcsh/login.mine) exit cleanly, without any errors. I cleaned mine up, and my history returned.
[Author's note: This is a feeble hint, but perhaps it will help people as stumped as I was. There was no indication of this problem from the tcsh manpage or the database of past hints.]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20020620225851954