Well, if you are using version 1.4.x then follow the following steps:

  1. First keep your design ready. you may use Photoshop or open source Gimp
  2. Identify the default theme which can be used to develop your own theme, say, if your design is similar like magnto default theme then its better to follow default theme than modern theme.
  3. Now go to admin panel, System-> Configuration->Current Configuration Scope:Main website->Advanced:Developer->Debug:Template Path Hints : YES and Save the button
  4. Also, Flush Magento cache then refresh cache and finally disable cache status as we can see in this image System -> Cache Management -> Disabled
  5. Now, look at frontend you would see something like below
  6. As I am developing theme based on default theme, so create a new directory in 
    \app\design\frontend\default

    , so if your new directory name is newtheme, then it will look something

    app\design\frontend\default\newtheme
  7. Copy all files from 
    app\design\frontend\default\default

    to 

    app\design\frontend\default\newtheme
  8. Similarly create a new directory in 
    skin\frontend\default\newtheme

    and copy all files from 

    skin\frontend\default\default
  9. Before I go ahead, lets activate our theme, go to admin System-> Design ->Add design change-> Custom Design: Select Default:newtheme and Save
  10. Well, Look at frontend carefully, this page is showing which template files are being used to show this page. Now if you need to change header then you need to change: 
    frontend\base\default\template\page\html\header.phtml

    file

  11. But we will not change anything in 
    app\design\frontend\base\

    directory, rather copy that header.phtml file and save it in

    app\design\frontend\default\newtheme\template\page\html\header.phtml

    create all necessary directories :)

  12. Refresh the frontend, you would see header template hints has changed to 
    frontend\default\newtheme\template\page\html\header.phtml

    file

  13. Play with 
    skin\frontend\default\newtheme\css\styles.css

    to change color scheme

To develop version 1.3 theme procedures are more or less same, but need to copy whole default directory to newtheme directory. You would see many files.

If you need professional help to convert PSD to Magento template, or upgrade (rebuild) theme then please visit PSDtoMagento.NET to get a reasonable quote.