It's something that is relatively easy to do, depending on your level of knowledge of XSLT, HTML and CSS. You have probably already noticed that the CQWP comes with a number of styles out of the box, that you can select through the web part properties.
The best way to style your CQWP is by adding new custom styles to this list. They are defined in a file called ItemStyle.xsl. You can edit this with SharePoint Designer, use it to open the top level site in your site collection and browse to /Style Library/XSL
Style Sheets/ and you'll find it in there.
When you look at the contents you'll see it contains a number of XSL templates, each one corresponding to one of the styles you can pick in the CQWP. To get started with your own style all you have to do is copy and paste one of the templates and give it
your own name (and update the 'match' expression to match it too).
If you haven't used XSLT before it can be an odd concept to get used to, but if you are familiar with HTML/CSS you should be able to see pretty easily how to add in your customisations and then go from there.
