Search for all nearest neighbors within a certain radius of a point in 3D?
My recommendation is NOT to roll your own for now. There are two software packages that I'd recommend you try first. 


ANN (by Arya and Mount) is state-of-the-art for low dimensional near neighbor search and includes the "fixed radius" search that you're looking for. 
Nearpt3 (Wm Randolph Franklin) is another package that is specifically optimized for 3D, and supposedly can handle 100s of millions of points. I'm not entirely sure it handles fixed radius queries as well as regular nearest neighbor search, but you can look into it. 


If neither of these is appropriate, then you can return and ask :).