Sometimes it's really hard to get started, but usually the problem you want to solve is in some fairly isolated subsystem and writing a sane patch only takes an hour or two at most.
Of course you sometimes step on someone's toes, but more often than not my patches just get accepted.
There are hundreds of reasons why they won't pull your changes. This doesn't apply to small, single dev programs. They are usually, at least in my experience, pretty happy that someone wrote a patch, but the big ones are really, really bad.
Basically, if upstream doesn't accept your patch, you have two options:
Either you really want to see your patch upstream. In that case you invest the time it takes knowing that your contribution will be measured by the same scale that everyone else's contribution has been measured with. You also know that your contribution will be usable and part of a stable project. And you'll be confident that it probably won't be your mistake taking hundreds of sites down that are using the project you contributed to and are now hitting a bug you introduced.
On the other hand, you can feel that it's not worth the hassle. That's totally fine. You'll just have to manage your patch on your own from now on (in the end maybe creating an even bigger hassle in the long run).
Git gave you a very nice toolset for merging patches to an externally updated project, so that should be way easier than it was in the SVN days.
What Github did was to actually make it possible to decide either way.
Before Git and Github, your options were to either have it integrated upstream or to be stuck with whatever version you were patching (due to severely lacking merge support)
This is often perceived as bureaucratic and timidity against changes, but usually this is nothing more than a self-defense against subtle bugs, unnecessary complexity and vanishing readability, for which big projects are more vulnerable than small projects.
I'd say you should start by contributing to a small project, where there usually isn't a lot of red tape to learn. And most large projects have extension mechanisms, so if you want to contribute to a large project, make a small stand-alone extension. Or contribute to someone else's stand-alone extension.
You need to download and get the code running on your computer, and configure everything to run correctly. You need to learn the ins and outs of how everything works. You need to install and learn about the code the project depends on (and, most projects will have numerous vendor libraries). You need to get acquainted with the main developers on IRC, so you don't step on any toes. You have to learn how they do bug ticketing, and you need to find bugs you can do. And your first code review? Trust me, it'll be painful. It's not easy to get started.
If I left my job today, would I continue to contribute? Sure. But only because I already have a foot in the door, and know my way around.
All that being said, I truly believe universities should require students contribute to at least one open source project- it's a great learning experience, and the projects and their users benefit from the volunteer labor.