I always carry a small Rhodia notebook in my back pocket. They have very sturdy covers and won't come apart or get torn up. Everything goes into it: todos, ideas, notes about things I've just seen, heard, or read. I also like to keep some of those post-it bookmarks and some stamps stuck in the back against the cardboard backing. When I come home everything gets dumped where it needs to go, like my daily todo list, address book, or whatever.

I also keep a few text files going with books to read, movies to watch, and sights and attractions I'd like to visit.

I should add that these notebooks are much cheaper than moleskines :)