Some skins truly stand out as works of art, as well as being great skins in general. Others, while impressive in other areas, don't quite reach that level of artistic merit. If you're just starting out, there's not a lot you can do about this - you can learn from various tutorials (see the links section), but some things are best learnt by practice. You're unlikely to produce an aesthetically stunning skin the first time you try.
But don't let that stop you trying - do the best you can to learn from the best. Study other successful skins and try to adapt the techniques you see in them to your own skins. Don't be afraid to ask authors how they did a particular effect - most will be flattered, and it's a great way to get to know other skinners in the community.
You may find that you're better at the technical side of skinning than making good graphics. If so, consider teaming up with a good artist who has some interest in skinning but doesn't want to bother with the nitty-gritty aspects. Odds are you can make a better skin together than either of you could alone. Conversely, if you're a great artist and want to get into skinning but don't have much interest in the technicalities, find someone who does and who admires your work, and you're set!
Alternatively, try creating a port from another user interface - perhaps from your favourite game, or from a skin designed for another skinning format. You can typically reuse most of the graphics and making the rest is easier once you have a style to work from. If you do go down this route, be very careful about respecting copyright - you must ask the original author for the right to distribute your skin if it includes or is significantly derived from their artwork, and try to add something that enhances it beyond the original.
Quick Hint: It's best to distribute porting permission with your skin - some skin sites will not accept ports without it. Even better, note their consent and perhaps a link to the original in your skin description - this lets them share the credit while gaining you a reputation as an honest porter. That way, everyone wins!
One other thing is to avoid putting any irrelevant images or text in the skin - for example, your name or logo. Think about it - which would you prefer to use all day - a branded skin, or a plain one? On the other hand, do use logos and the like when they're appropriate to the topic, like the game logo below - just make sure you have permission to use them beforehand. Companies can be very protective of their logos.
This logo is appropriate as it represents the game - however, it has been dimmed and blended into the background to avoid appearing clickable or distracting attention from the buttons, which are a different colour and highlight on mouseover to emphasise clickability.
bordfryr123: "I DON'T like skins that have someone's name, logo or the name of the skin in a very noticeable place. I have bypassed using numerous skins for these reasons."
I.R. Brainiac: "I DO like seeing the name of a skin in the work somewhere. It's a unique identifier. However I don't want to see the name of the person anywhere."
Finally, be sure to take advantage of vectors, layers and other abstractions offered by your graphics program. These can save you time and effort when you need to make changes to your skin (and you will!) and enable you to offer different versions with ease. If you don't know what these are or how to use them, take the time to learn - as a skinner, time spent learning to use your tools is well worth it.