Expanses of water will reflect the sky, giving added interest to your images.
But you do not need lakes or rivers - focus on puddles in the street after a rainstorm for a similar effect or even wet sand by the sea.
Reflection, © Fernandodelopey 2011, Canon EOS 30D
Black & white
Clouds within skies naturally lend themselves to black & white photography. This can be done in post processing or within the 'Picture Style' settings on your EOS.
Graphic design, © Dario Bonetto 2011, Canon EOS 40D
Sunrise and sunset
Cloud formations often appear particularly dramatic at sunrise and sunset. The warm glow of the sun can diffuse through clouds giving shades of orange and pink that will add colour to your images. Exposing just for the sky can work well, with the ground dark and often in silhouette.
Sunset, © Rolf Pahnhenrich 2011, Canon EOS 5D Mark II
Rule of thirds
Just like other photos, the rule of thirds applies for photographing skies. Whilst typical landscape photos will have their skyline one third from the top, you should consider it being 1/3 from the bottom when photographing clouds and sky. This is demonstrated well in the image above. The two vertical lines of the grid are also still important; they can be used for a relevant object in the foreground.