I went up there digging for records a couple of years back and had quite an interesting run - mainly because I got speaking to a guy in a record shop in this Afflecks'y shopping arcade and he said he had a few thousand records upstairs he hadn't got anywhere to put them out; I persuaded him to let me look through them and ended up with several crates of 12"s at £1 each - a lot of stuff which probably hadn't seen the light of day for 5 or 6 years :) I think that place was upstairs in "The Forum" but I wouldn't guarantee it. There was also a drum and bass shop downstairs there with a good selection... That was on the end of a street which seemed to be the main street with record stores on it which I believe was Devonshire street. You also have down there a record shop in the back of a girls clothing shop (small selection of new dance releases leaning towards funk reissues and IDM-type stuff); old-hippy-who-only-knows-about-rock-music-except-the-orb-as-it-is-in-the-price-guide run secondhand record shop with a small selection of crappy dance records overpriced; big independent shop with a lot of cheap vinyl on the second floor (think it might be Fop); plus a few more stores... I checked a few other places throughout Sheffield but there was nothing significant except one place on the other side of the city whose name escapes me! You'd probably find it most rewarding to stay on that one street...
There's also a place called Polar Bear which I have bought quite a bit from by mail order over the last year or so... No idea where it is but they get some quality secondhand stuff in! I found this on the net which may help http://www.knowhere.co.uk/518_music.html David