With clever use of gradients and mirror effects in illustrator or freehand you can get the skeleton for these. The last step, color effects, is definetly photoshop or fireworks. The smoky effects around these are usually enlarging the images and adjusting the opacity.
I don't really know of any tutorials. #2 to me looks like someone used a picture and did filters on it. #4 very well may have started out in a vector program.