Okay, I've been fighting the good fight with Blender for a few weeks trying to convert some models I originally created for rendering into a printable file. I've learned a lot in the process, so I thought I'd share some of what I've learned. Forgive me if some of this is obvious. Most of it, I was not able to find when I was looking, though I am admittedly not the most experienced Blender user in the world.
If you have a model created from several objects or meshes, first make sure that each individual mesh is manifold (water-tight). You can tell this by going into edit mode, pressing A (once if any vertices are selected or twice otherwise) to select none, then hit ctrl-alt-shift-M (on a Mac it's ctrl-opt-shift-M).
Any vertices that get selected when you press that key combination are non-manifold vertices that have to be fixed. Often, fixing these is just a matter of creating new faces (F key) out of sets of 3 or 4 vertices. Sometimes these are stray vertices that are unattached to anything, or are attached to just one vertex by an edge. These can usually be deleted, unless they are intentional (such as those vertices uses to affect the shape while using a subsurf modifier), in which case you want to wait until after you've applied your modifier to delete them. Another possibility are vertices that are part of more than one overlapping faces.
If there are three or four attached polygons that it says are non-manifold, but says there is already a face, try deleting the face and, if necessary, recreating it. Also, look for edges from any of those non-manifold vertices that don't seem right - that aren't part of the mesh proper or kick off in an odd direction. Sometimes you just need to delete a chunk and patch it up manually.
One trick that makes things easier is to select non-manifold, then press ctrl+ several times to increase the selection. This will select the non-manifold vertices, plus an area around then. Then press shift-H to hide the rest of the vertices, so the part of the mesh that's unaffected by the non-manifold problem are hidden, which will make things faster while fixing and less confusing.
Once you've got all your meshes manifold, make sure that every mesh is its own object. You can't do boolean operations between meshes within one object. You can split part of a mesh into its own object by selecting all the vertices in the mesh and hitting the P key. Selecting a single vertex and then holding down ctrl-+ will select all attached vertices. To separate each mesh in the current object at once, press P and select 'All Loose Parts'.
Once you have all meshes in their own objects and manifold, save and create a copy of the blender file for making the printable version. I also set Blender to keep the past 10 saved versions because I'm paranoid - I like being able to go back and retrieve older versions of the meshes if I screw up beyond the undo threshold.
Open the copy of the file, and select each object, one at a time. In object mode, apply all modifiers, then switch to Edit mode, hit A once or twice to select all vertices, then press ctrl-T to triangulate all faces. I don't know why, but Blender does a much better job with Boolean operations if the meshes are triangulated.
Back in object-mode, select any two overlapping meshes, press w and select "Union", which will combine them into a single mesh (it doesn't delete the originals, though). This process could take a while. Once it's all done, select the two original objects that were combined, and either move them to another layer, or delete them to get them out of the way (I delete them, but that's why I keep the last ten saved copies). Select the new combined object, switch to edit mode, select none (A key once or twice), then select non-manifold (ctrl-alt-shift-M). Resolve all non-manifold, many of them will be easy to fix, and often a union will result in a manifold mesh, but not always, so always, always check - if you move on and try to do another union with a mesh that is non-manifold, you will have problems. Check for manifold EVERY TIME. After that, select-all and triangulate so your combined mesh is both manifold and fully triangulated so it's ready for the next union, if necessary.
If you have two meshes that have a widely disparate density of vertices, like an organic mesh being unioned with an eight-vertex cube, subdivide the one with the lower density and then triangulate. For some reason, Blender does not like doing these types of unions - it will chug away for hours and hours and probably never finish.
Save every time you perform a union then resolve the non-manifolds.
Once you're down to no overlapping meshes, and each distinct mesh is manifold, scale your objects to the size you want, assuming 1 blender unit equals one millimeter.
Now, check the status bar for the number of faces (it'll look something like Fa:123456 - the number next to Fa: is what you're looking for). If there are more than 500,000 triangles, use the Polygon Reducer Script under the Mesh menu in the Script pane to reduce the face count to below 500,000.
Next, rotate the object 90° on the X axis. Blender uses Z-up, Shapeways go with the more common Y-up rule, so if you don't do this, your model will be oriented wrong in the shop gallery picture.
Finally, export to STL. When uploading the file, make sure to select "millimeters" for scale.
If all went well, it'll upload, and you'll get notified that it's ready for printing.
Hope that helps somebody out there. Took me a lot of pain and time to get my stuff printable.