Autoloading is just a method to replace "import every needed class/method/library" with "if you put files in a particular place, we can find them".
The basic algorithm is something like "if you use a class or module and it's not found, before we tell you we can't find it, search for it in one of these paths."
Autoloading is orthogonal to finding gems, but rather in finding your application's code. In other words, your gems are loaded and required from your Gemfile once, at app startup, but the autoload mechanism operates not on gems, but on your app's code.
So to answer the first part of your question: gem loading is not directly related to autoloading. Including new gems to your app might make app startup a bit slower as the library is found and parsed, but they're loaded for all time after startup; it won't affect your per-request performance.
It's good to know that RubyGems are a part of Ruby, and autoloading is a part of Rails: Rails is a framework written on top of Ruby, the same way Django is a framework written on top of Python, but Ruby and Rails are very distinct. Gems are a part of Ruby and autoloading is a part of Rails.
Autoloading is meant to make development faster; instead of having to restart your server every time you make a change, if you follow the directory layout convention, your files (and only the files in your app) will be reloaded on every request. This is good, because you can just leave your server running as you develop.
It's worth noting that this is true in development mode only. In production mode, it will find the file if it's missing only once and remember it across requests, in order to save you the overhead of filesystem searching on every request. In fact, if you're using Rails 3.2 or above, it's become smart enough even in development mode to only reload the file if it's changed since the last request, making things even faster during development.
You don't have to use autoloading, btw: you can manually require the files you need, just like you talked about with Python. This is the standard Ruby way of doing things. This will circumvent autoloading that file entirely, since your constants are never "not found": this is good in that it will increase performance of your app, but bad because you'll have to restart your app every time you change your code.
tl;dr: don't worry about autoloading performance. It will help you in development mode at the cost of app performance, and be performant in production mode at the cost of development speed.