How much would I actually need to know about a programming language before it could get me a job?
I've been learning some Java on my own. I can output the hell out of some Fizzes and Buzzes and if you give me a minute I could even get you the n-th element of the Fibonacci sequence, but... I'm assuming in a real life scenario I won't be getting an urgent message from a bank that really needs to know which one out of the two given numbers is the larger one.
The tutorials I'm reading are all teaching me basic math and logic, which are obviously important, but at the end of the day I still feel like I don't actually know anything. A checklist or something would be pretty sweet.
On Java:
Pick up a Java certification book. Outside of a good introductory book like Hortsmann's book or a Head First, I find cert books are a great way to learn Java. They are structured as learning tools. You get an explanation of some concepts, then exercices, then more explanation, then more exercices, etc. They start with the most basic things, and go all the way to the essential ones, and they give you insights into the pitfalls and quirks of a language.
On working as a programmer/software dev:
As you have found out, knowing a language does not mean knowing how to program or how to develop software.
Read The Pragmatic Developper and Code Complete 2.
Another thing you could look into is Java Interviews Explained. It covers computer science topics like algorithms, data structures, etc., and how to know your stuff.
Since you are targeting Java, try to find a book that explains object oriented software development. A guy I knew had a book that went through the development of a full application from requirements to modeling to development. I can't find it but something like that would be good.
Finally, a word of caution on design patterns. Try to avoid using patterns for now. IMHO, they are an advanced topic. I mean, look into it, know them well enough to understand how some programs and APIs are structured but don't use them. A huge problem in Java is that people hear about patterns and how they are these magical train tracks to the best programs ever. These same people then break down their requirements to fit patterns. Hilarity ensues. They end up with overly complicated programs that are hard to maintain, hard to understand and, hard to expand. Everything patterns are supposed to help you avoid.
Things like this old joke : )
Are you familiar with AbstractSingletonProxyFactoryBeanInterfaceModuleObserverStrategyPattern?
(I just made that up but it might be a real Java thing)
Patterns are very important to solve problems and improve the structure of applications. However, there are a lot of basic concepts to master before applying patterns.
"The simplest thing that works." and "Done is better than perfect." are two mottos to keep mind.