The simplest way to change Sputnik's appearance is to change the color scheme. You can do it by setting a single configuration parameter (MAIN_COLOR) to a value between 0 and 360. Read Color Schemes to see how this works.
For more advanced changes, edit sputnik/css/colors and sputnik/css/layout.
If you need to actually change what HTML is generated, move on to Templates.