Over voltage on Arduino and Ardumoto
From your description, everything should be wired correctly. It should not have failed.

Unfortunately, testing this sort of thing with a 5 amp-hour lead-acid battery is not a great way to get started, since a battery that large can source a lot of current, and doing anything wrong will likely produce immediate and spectacular failure.

Really, the only think I can think of is that you have the polarity of the output lugs/pins on the battery backwards. Buy a $5 multimeter, and check them.