How does an engine decide which node to search first? This is a follow-up question to Randomness in Engine Play. SmallChess's answer indicates that in one instance, Stockfish searched a given number of nodes after 20s, and a different number in the other 20s, hence there is randomness.

The question: if each node is a given position, how does Stockfish decide which node to search first? Take for example the first half-ply. White has 20 possible first moves, so there are 20 nodes. I demand that Stockfish play a move after searching five nodes. Does this mean that Stockfish might only have evaluated 1. a4, 1. a3, 1. b4, 1. b3 and 1. c3 before it has to make a move? A systematic search like this would mean Stockfish hasn't evaluated the most common first moves however.

I imagine that, later in the game, there'd be a massive jump in the number of nodes per half-ply. That would mean that Stockfish would sometimes decides to make a move even though it hasn't finished evaluating every node in the half-ply. How would it know that it's searched the most promising nodes?
http://rebel13.nl/rebel13/ideas.html explains this well.  

The basic idea is to order the moves based upon what the program thinks is the best move without searching.  This score is usually based upon mobility, piece-square value, center control, history, attacking potential, captures, and other elements the programmer thinks is important.  Just as humans base their candidate moves based on intuition and history, the computer searches the highest scoring move first.

If the computer is limited to only five nodes, then yes, the computer will only search the five highest scoring moves.  This time limit factor could cause to computer to miss a mate-in-one if it was scored poorly.  The first method to correct for this was to establish fail-safes.  These would cut short a search if the position became noticeably worse or significantly better.  The hope was to allow for more time to search more variations that might use the time better.  Other search algorithms, iterative deepening,  have improved the time management as they have a shorter length before they enact a fail-safe.