It would be expensive on a complete floor that's already in place, but in-floor hydronic heating is the cat's meow. I've got a few buddies with shops with heated floors and it's a luxurious thing when you're working under a truck.
Gas fired radiant heaters like Craig suggested would work as well. Or Electric radiant.
For a much less expensive option, how about a thick rubber pad in front of your workbench? That would at least insulate your feet from the cold floor. I don't know if anyone makes a heated pad, but that would be even nicer.
