When to use TINYINT over INT?

Disk space is cheap... that's not the point!

Stop thinking in terms of storage space, think instead about buffer pool and storage bandwidth. At the extreme end, CPU cache and memory bus bandwidth. The linked article is part of the series highlighting issues with poor clustered key selection (INT vs GUID vs Sequential GUID) but it highlights the difference bytes can make.

The overriding message is design matters. The difference won't show up in an individual database on an appropriately spec'd server until you hit VLDB territory but if you can save a few bytes, why not do so.

I'm reminded of the environment described in an earlier question. 400+ databases, ranging in size from 50mb-50GB, per SQL instance. Scrubbing a few bytes per record, per table, per database across that environment could make a significant difference.

In addition to the other answers...

Rows and index entries are stored in 8k pages. So a million rows at 3 bytes per row isn't 3 MB on disk: it affects the number of rows per page ("page density").

The same applies to nvarchar to varchar, smalldatetime to datetime, int to tinyint etc

Edit, June 2013

http://sqlblog.com/blogs/joe_chang/archive/2013/06/16/load-test-manifesto.aspx

This article states

The important criteria are the cardinality and the page to row ratio.

So, choice of data type does matter

It's not only table storage that is a consideration. If you use indexes where the int column is part of a compound key, you would naturally want the index pages as full as possible, this being the result of index entries being as small as possible.

I would definitely expect to find that examining index entries in BTREE pages would be a little faster with smaller data types. However, any VARCHARs involved in index entries would offset (nullify) performance gains from using TINYINT over INT.

Notwithstanding, if index entries have compound entries and all are integers, the smaller the integers are bytewise, the better and the faster.