I'm aware characters can rest to regain health and fatigue, but when exactly does a character get fatigued?
There aren't actually rules for this. The closest thing we have is this:
From Sleep (PHB 263):
However, this doesn't really tell us when an adventurer is fatigued. The truth is that there really isn't a rule for this. That's up to your DM. The only hard and fast rule here is that to get the benefits of an extended rest you need a 6hr nap (this also means that if you have other things to do during an extended rest, it might have to be longer than 6 hours, so you can get your full sleep in).
As far as tracking when a day ends and when a day begins, this is sort of something you can let the players dictate in most situations. There might be some situations where you intentionally prevent your players from taking an extended rest (it's not safe, there are consequences etc), but generally, you want to let your players rest when they feel like they have an opportunity. The game is designed around adventuring days consisting of 4 or so encounters, though many adventuring parties can take on more than that if they need to (but resources will likely look very thin by the end).
The rulebook says that you can't start a new extended rest until 12 hours after the previous one, so if you're trying to figure out how much time is past, consider each extended rest to be the passage of a full day. most of the time the combat or skill challenge portion of a day will be very little, more likely your players will spend the majority of their time traveling or with other downtime.
Usually you don't need to know about fatigue, but you need to know whether a character is able to continue whatever he wants to continue doing. So I would recommend looking up the rules for Endurance skill checks. For example a character needs to do an Endurance skill check if he wants to swim for over 1 hour, or row for "an extended period".
You could say that if he fails such a check, the character is fatigued.