Shane, congratulations on successfully getting your engine on the stand. Now the real fun begins!
Disassemble down to the bare block. Mark the pistons and connecting rods with the cylinder number that they came out of, in case they are reused. The same goes for the lifters, pushrods, rocker arms and valve springs. Mark each one with it's location in case it is re-used. Again, nuts, bolts, and small parts go in freezer bags with LABELS!!
As for cleaning, the machine shop should have a "hot-tank" of cleaning solution that they can dip the whole block, head, and other metal parts in. This dipping cleans out years of crud buildup inside and outside the engine. Sounds like your engine is pretty clean on the outside, but who knows whats lurking on the inside? This solution should also remove any leftover paint.
Once they have the block cleaned, they can magnaflux and check for taper. There is a good chance that your head is cracked, these heads were prone to cracking.
It can be repaired if it isn't too bad. The block is pretty tough, it's rare that one is cracked.
The best thing to do is to talk to your machinist first. He (she?) can tell you what they would like you to do before you bring the engine to them. They sometimes disassemble the engine for you if you want (for a small fee!).
Check out this link for a good rundown on disassembling and rebuilding a Chevy Stovebolt.
Chevy Stovebolt Engine Rebuild Steve
