Where do I start for Arduino PCB design?
I started learning a PCB designing software and successfully made a working PCB prototype containing two Arduinos, RTC, external EEPROM, RF module and some other components on a single board all within two weeks.

This is how I did it:

Selection of PCB designing software - I chose Eagle because:


It's free but with a limited board size (not a big deal for most of
the hobby projects)
Huge community support as compared to other softwares (because it's
free)
Most of the open source hardware schematics and board layouts
available in Eagle format. Ex Sparkfun releases eagle schematics and
layout. Arduino available as well.
Learning was quite easy.


What electronics concepts to learn: As you mentioned, you are a software guy, you need to do a little reading before you start developing complex projects. This is necessary and it'll pay off. 


Power regulators - Here you need to learn about linear regulators and switching regulators. Which one to use and when.
Decoupling capacitors and their proper placement on a PCB.
Diodes and their uses - Voltage clamping, reverse polarity protection etc.
Pull up and pull down.
Filtering capacitors.
Benefits of having a good ground plane. (I underestimated it once. Paid the price.)


What software concepts to learn: Obviously you need to learn most of it to make a PCB. But here I'll highlight some concepts you should know even if you don't need it in your first project. This will come in use at some point for sure.


How to make a component on your own.
How to make a custom library.
Copying symbols and packages from other libraries to your library.
How to use ULPs. In eagle, there are ULPs to automate some tasks. I haven't explored much but I have used one which extracts all components from any schematic and dumps them into a library so that you can use it in different projects. That's how I got Atmega328p. I was unable to find it in default libs so I extracted it from Arduino's schematic.
How to make a logo - You might like to have a custom logo on your PCBs.


Production part:


Once you are done with your schematic and board layout, you  need to export Gerber files to be sent to the production houses. It contains all the info in a numeric form which can be understood by their machines. Eagle will do it for you. Find this in Cam processor section. Sparkfun provides a Cam job file but don't hesitate to modify it to suit your needs.
You need to select a PCB thickness and copper layer thickness. For low power, 1-2 mm PCB with 35 microns of copper will do the job easily. You can also specify the mask color if your production house allows you to.
Most of the production companies provide prototyping of PCBs. This is costly but there doesn't seem to be an alternative. They will charge you more if you want it to be delivered quickly. Make sure you talk to 5-10 production houses before selecting one. Their prices vary wildly. In my case, one was asking 10 times the price quoted by the other. No kidding.
Component selection - Through hole or smd? Both have their pros and cons. SMD will allow to make compact and neat boards but they are relatively difficult to solder on your own. However if you select relatively larger footprints (1206 or so), it shouldn't be that hard. For a start, I'd suggest through hole components. Pretty easy to handle.
Verifying your Gerbers: Before you send the gerber files for production, you can verify them by using softwares available for free. I use GerberLogix.


Tip: Before sending your first board for production, post the schematic and board layout on forum so that you can get suggestions/opinions from people who are experienced in this field.