Note: I obviously have the benefit of a nice location. Depending on where you are there may well be nothing like this. However, as others have said location does matter, so spending some time trying to find any places locally with a decent view in the right direction could be time well spent.
I find it difficult to get shots I like when the sun is clearly visible, and so before the sun has set I seem to get much better opportunities when the sun is more or less obscured by clouds. You are using a better camera than me (I am using a tiny sensor bridge camera) which may handle this situation better, and your visual tastes may differ, so I don't know how much this might be an issue for you.
5.1 IMG_0023 PS1 by
gardenersassistant, on Flickr
(The sky was actually pretty unpromising that day, mainly empty of clouds, with only a fairly featureless cloud bank along the horizon, but I stuck around anyway, and in came this other cloud at just the right time. Some days are definitely more promising than others as far as the clouds go, but as to what will actually turn up on any particular day - there seems to be a large element of randomness/luck, for me at least. Moral? Keep trying, be there, and ready, but don't be put off when nothing much turns up. When things do work out, it can be absolute magic.)
I have found that quite often the best (to my eye) sunset opportunities arise in the 10-20 minutes (-ish, I've not really timed it consciously) after the sun has set. Sometimes there are great colours for a few (it can be very few) minutes, for example on days when the clouds higher in the sky turn pink. This can happen when the sun has gone down beneath the horizon, or when it has gone behind a low cloud bank, as in this example.
2.07 Sunset28 APP1 HoPSD16 PS1 RoWaShHiCuDf61600wSS1.20 by
gardenersassistant, on Flickr
And sometimes what I see seems to be rather deceptive - light levels and contrast drop fast once the sun has set, and quite quickly it can look as though there is nothing worth photographing. However, even with my camera settings set at or near their minimum values, the camera quite often seems to "make more of" the post-sunset skyscape than my eyes do, in terms of both colour and contrast. And a little PP can sometimes help in this respect too (without needing to go over the top, and FWIW the more sunsets I photograph the less I seem to do to them by way of PP).
BTW, be aware that colours may go haywire for sunsets. For example, I often get yellows in the images that are not there in reality, and on the other hand there is sometimes a beautiful turquoise colour in the sky that I have rarely if ever been able to capture. I think the yellows are to do with overloading the sensor. Here too, your camera may handle this side of things better than mine.
On the subject of dull (low contrast and pallid colour) post-sunset skies - I have found it best not to leave the scene too quickly, as the sky can sometimes go through a very dull ("it's all over") period before colouring up very briefly. For example, this is how the sky looked about 10 days ago not long after the sun had dropped behind the distant clouds (and the real world light level, contrast and colours were I think significantly duller than you would think from looking at this).
0341 10 2011_02_07 IMG_9953_IMG_9961-8 images APP1 PS1a ClSa1200wDf7x30 Df7x30 by
gardenersassistant, on Flickr
And this is what it looked like 11 minutes later.
0341 12 2011_02_07 IMG_0006_IMG_0009-4 images APP1 PS1 SaShDf4x301200w by
gardenersassistant, on Flickr
Also bear in mind that sometimes there are things going on in the sky on a pretty large scale, large enough that you may not capture them even with a very wide angle lens. In any case, I use a bridge camera and don't have the option of using a really wide lens, so I use panos a lot for sunsets (and non-sunset skyscapes). Depending on how the clouds are arranged, I go up to 360 degrees horizontally and up to 90 degrees (perhaps more) vertically (which means using more than one row of images). Here is an example of one of these larger-scale structures in the sky. This image covers about 270 degrees horizontally. I'm not sure about the vertical dimension, but it used three rows so it was quite tall.
3 Sunset12a APP1 RoLeGaPSD16 PS1 WaSelBr+Df+**+SaInvSelBr1600wSS1.15 by
gardenersassistant, on Flickr
I also find it pays to keep looking all around the sky, as sometimes there are smaller things happening (also sometimes very brief) that catch my eye as the shapes and lighting change. Here is an example.
4.8 IMG_9986 PS1 by
gardenersassistant, on Flickr
