Is it possible to move sharing rules from one environment to another WITHOUT having to recreate it manually in Salesforce? I read somewhere that Force.com Migration Tool can be used to transfer these metadata as well.
Its definitely possible using Forc.com migration tool or changset .
The changeset components will consists of the sharing rule both criteria and ownership based for custom and standard objects .Looks for them in the changeset.
If you want to move via Force.com IDE or ANT migration tool you can use package.xml
<?xml version="1.0" encoding="UTF-8"?>
In force.com IDE you will see a folder named SharingRule that you can deploy to the other org .