I believe (but haven't actually seen myself) that some RDBMS's have builtin support for this kind of thing; check out what (the latest version of) your RDBMS has to offer.

I've given some thought to how I'd do this before, and come up with the following:

Pretend the earth is flat. Divide it up into equilateral triangles, each with an id and lat/long of the center. Add the triangle id to your records; if any triangle ends up with an unwieldy number of distinct lat/longs, divide that triangle into 4 sub-triangles like so:

____________
\    /\    /
 \  /  \  /
  \/____\/
   \    /
    \  /
     \/
[download]

Then select triangles that may contain points in your range, and select records with those triangle ids. If complete accuracy is needed, end by filtering out records not actually in your distance.

I have the feeling database vendors do something like this if they support indexing lat/longs.

Update: why triangles instead of squares? I have a gut feeling that it will produce fewer outside-the-distance results, but am unable to say why.