I've been curious about how the popular website MySpace manages to pull off its "search by distance" functionality using such a huge set of data. Sofar I've thought of a few options:

1) Do calculations with every query:

SELECT u.username,
SQRT((POW((69.1*(zd.lon-zd2.lon)*COS(zd2.lat/57.3)),2)+POW((69.1*(zd.lat-zd2.lat)),2))) AS distance
FROM zipdata zd, zipdata zd2
RIGHT JOIN users u ON u.zipcode = zd2.zipcode
WHERE zd.zipcode = 55431
AND (POW((69.1*(zd.lon-zd2.lon)*COS(zd2.lat/57.3)),2)+POW((69.1*(zd.lat-zd2.lat)),2)) > 10

Surprisingly, that is a very fast query. 30ms including transit.

2) Create a table with pre-calculated values selected into it.
a. see if the desired zipcode has been selected into the zipdistance table. If not, run the same query as above, only remove the distance limitation and insert it into zipdistance:

INSERT INTO zipdistance
SELECT zd.zipcode,
zd2.zipcode,
SQRT((POW((69.1*(zd.lon-zd2.lon)*COS(zd2.lat/57.3)),2)+POW((69.1*(zd.lat-zd2.lat)),2))) AS distance
FROM zipdata zd, zipdata zd2
WHERE zd.zipcode = 55431;

b. use zipdistance for the cross reference:

SELECT u.username, zd.distance FROM zipdistance zd
RIGHT JOIN users u ON zd.zip2 = u.zipcode
WHERE zd.zip1 = 55431
AND zd.distance > 10;

This method also requires 30ms including transit.

Conclusion
While one would think that solution 1 would be unbearably slow, it is actually quite fast when a JOIN operation is performed. My guess is that the optimizer only compares records that it finds in user zipcodes. So really since my dataset is small each solution is the same speed, but as the set of user data grows the database will have to compare more records and thus be slower to calculate (sol 1) than to lookup values in zipdistance (sol 2).

One final thing to keep in mind: if you're using PostgreSQL, remember to VACUUM your tables!

Sources
http://www.sanisoft.com/ziploc/ - zipcode latitude and longitude data and some sample code for getting all zipcodes within radius

Table structure for zipdistance:

CREATE TABLE zipdistance
(
zip1 int4 NOT NULL,
zip2 int4 NOT NULL,
distance float8 NOT NULL
)