How do I control a two 12VDC 10A motors using an Arduino?
Take a look at the Pololu High-Power Motor Driver 18v15. It would seem to meet (and even exceed) your needs. I purchased one of these last week and it should arrive tomorrow. I'll edit this answer with my review.

3/27/13

Got it in the mail late yesterday. Assembled it tonight. Will be testing it out tomorrow.

4/7/13

My time with the switch was short yet incredibly productive. The boat in which the switch was placed eventually sunk taking a GPS, XBee, Arduino, and the switch with it. The switch was really easy to get up and running with. The soldering was quick and the provided capacitor worked nicely for my purposes. My battery's positive terminal connected to the V+ header and the negative terminal connected to the GND header. The motor's leads connected to the OUTA and OUTB headers. The polarity doesn't matter on those two headers as the device is capable of switching it.

On the logic side I connected the Arduino's GND pin to the switch's GND header. I didn't make use of the FF1 and FF2 fault flag indicators but reading them is as simple as a digitalRead once they're connected to the Arduino. The RESET pin is really easy to use. Just use digitalWrite(resetPin, LOW); to put the board into sleep mode (this also clears any faults). Bring it back up to high to resume normal operation.

There are two ways to operate the board but I'll only discuss the one I used which I believe is simpler. The DIR pin needs to be considered digital. So you set it up just like you would any normal digital output pin on the Arduino. You pull the pin HIGH for one direction and LOW for the opposite direction. This effectively reverses the polarity on the OUTA and OUTB headers. The PWM pin needs to be connected to a PWM-supported pin on the Arduino. On the Arduino Uno these pins are 3, 5, 6, 9, 10, and 11. Make certain that the pin that you choose is not being obstructed by a timer interrupt. Controlling the speed of the motor is as easy as using analogWrite on the pin with a number from 0 (stopped) to 255 (full speed). The map function will be really useful here. You can use it to take any sane range and convert it to the range you need (in this case 0-255). I used it to take 0-255 down to 0-100 to create a thrust percentage I could display but in that case I could have just divided the the number by 2.55. ;) Check out this commit on GitHub to see how I implemented it. Contrary to that commit, you do not need to use pinMode on the PWM pin.

The only "issue" I ran into with the board was that when running the motor it would create an audible tone depending on the speed. At full speed it wasn't noticeable but at lower speeds you could really tell. I didn't fix this issue before the boat sank but I'm told it can be resolved by using the Arduino PWM Frequency Library.

I hope this helps you and have fun with the motor driver. I would definitely buy another if a situation called for it. Definitely take a look at Pololu's product page for a very detailed explanation of the entire chipset.