Start by implementing spatially inhomogeneous atmospheric attenuation. Divide each ray into intervals. For each interval, interpolate between the ray's color and some constant fog color based on a procedurally computed opacity for that location in space. Experiment with opacity functions. Implement a class of more complicated primitives from Hanrahan's chapter in Glassner's book.
Fractals are relatively easy to implement and fun to use.
For extra fun, map textures onto your patches or fractals. Look at Hanrahan and Krueger's Siggraph '93 paper. Exotic wavelength-dependent effects. We can give you some references. Mimic the object's appearance as closely as you can.