However, how exactly does the system determine that bitcoins that were previously nonexistent should be awarded to whoever solved a block?
That was decided when the system was designed. Everyone knows it now because it's part of the public specification. The block reward schedule is well known and well understood.
It's no different from how we all know that a nickel is worth half as much as a dime -- if you want to use US coins, you have to know and understand that rule because everyone else follows it. Everyone who wants to use US currency has to learn the rules, otherwise others won't accept their payments.
My understanding is, once all bitcoins have been mined, the only way to gain any profit from mining is through fees that were voluntarily added to a transaction. How does the system right now know that this is not the case for a given transaction (or a group thereof) and that it should instead create new coins "out of thin air" to reward the workers?
How do people know a nickel is worth less than a dollar? If you want to use a currency, you have to learn its rules. You must know the value of a nickel or you can't properly credit and debit payments that use nickels. You must know the relative value of dollars and pennies. And so on.
These are the rules of Bitcoins. If you want to use Bitcoins, you (or the software you use) must understand the block reward schedule, otherwise it won't be able to properly credit or debit payments.
There's nothing complicated or mysterious about it -- it's just the rules everyone else has agreed to, and thus the rules you must agree to if you want to exchange Bitcoins with other people.
