Question: So I've had at least two professors mention that backtracking makes an algorithm non-deterministic without giving too much explanation into why that is. I *think* I understand how this happens, but I have trouble putting it into words. Could somebody give me a concise explanation of the reason for this?

Answer: 
I wrote a maze runner that uses backtracking (of course), which I'll use as an example.

You walk through the maze. When you reach a junction, you flip a coin to decide which route to follow. If you chose a dead end, trace back to the junction and take another route. If you tried them all, return to the previous junction.
This algorithm is non-deterministic, non because of the backtracking, but because of the coin flipping.

Now change the algorithm: when you reach a junction, always try the leftmost route you haven't tried yet first. If that leads to a dead end, return to the junction and again try the leftmost route you haven't tried yet.
This algorithm is deterministic. There's no chance involved, it's predictable: you'll always follow the same route in the same maze.
If you allow backtracking you allow infinite looping in your program which makes it non-deterministic since the actual path taken may always include one more loop.