I don't know how you are drawing, what libraries you are using...
In DirectX and OpenGL, you usually use vertex and index buffers to hold your geometry data. If the triangles in whatever format you are storing them in are still in the order of the quads they appear in, as is the case with at least some OBJ exporters, it can be relatively easy to figure out which vertices form a quad.
For example, in an obj file, a quad with the vertices 1,2,3 and 4 that was translated to triangles upon export might look like this (pseudo code):
f 1 2 3
f 3 4 1
which would look pretty much the same in your index buffer.
A very simple solution would be to keep a second index buffer for your quads,
where you could store the indices 1,2,2,3,3,4,4,1 or even 1,2,3,4,1. In directx there are the linelist and linestrip topology types which would render these indices as lines treated with your regular shading.
If you create your own file format for storing models in, it becomes easier as you could store quads where possible and tris when necessary in the file, and only translate them to triangles upon import.
I've done this, and since I usually create my 3D models with quads and only use tris where necessary I find a quad wireframe much more intelligible. It is relatively easy to implement provided you are lucky and your storage format accomodates you, but it does have a number of drawbacks.
For one thing it does not produce thick and soft wireframes. It also does not produce a shaded wireframe, but a completely transparent one, so to have your wireframe ontop of your regularly shaded geometry you would have to first draw your object and then draw your wireframe, so there is a performance hit. Still, even drawing the objects twice, once shaded once as wire, this still performs better than just directx' wireframe RasterizerState setting alone. This method is also likely to create z-fighting, which might make it necessary to increase the scale momentarily to avoid that.
Here you can see how it looks in my test implementation, you can see both the z-fighting and the moire patterns created by the aliasing of the lines (there are ways to draw antialised lines though):
http://i.stack.imgur.com/N6X3Y.png (sorry I can't embedd images here yet)
All in all nvidia's solution David posted looks very interesting, I've seen it in the samples and I've been meaning to take a closer look at that.