Pilots n Paws Canada has program called Petscorts that matches people flying with animals that need to be moved. These animals are usually being moved from one rescue to another where they have a better chance of being adopted (e.g., a Border Collie in a Quebec humane society might get moved to Manitoba to a Border Collie Rescue).
Petscorts takes care of everything, including handling the paperwork and costs. The tack on the checked animal booking to your reservation. A volunteer meets you at the airport to check the animal in, and someone meets you at the other end. It's very easy, and you get thanked a ton! I've done it several times for them and it's been great.
PNPC is a registered charity in Canada, and they only do domestic flights.
For more information:
http://www.pnpcanimalrescue.ca/
You can use their contact form, or I can pass along an email address if you would like to register your flights with them so they can match you up.
Thanks!