> How do those that can play "fluently" know which keys to press?
There are a lot of possibilities. I'll take a stab at one.
Let's say I want to play The Eagles' Desperado on the piano. Here's what I'm doing in realtime:
* I start singing the melody
* I visualize a piano keyboard and imagine the note where I start the melody
* I play a note on an invisible keyboard in the air with my right hand
* for each note I sing, I move my fingers synchronously to play the corresponding note on the invisible keyboard (right hand only)
* I get comfortable doing this. If my hand goes to a note that I feel uncertain about, I do a quick sanity check to make sure my hand is still playing the correct invisible note to correspond with what I'm singing.
Here's a simplified example of the error correction-- if I'm in C major and I know I'm singing middle C, I make sure my hand is playing an invisible middle C. If it's instead playing a different note then I messed up somewhere along the way. Playing and identifying the pitch "C" when playing in C major is really easy to do, so it makes a good anchor point for beginners. In practice I've got about three types of anchor points that I can track in realtime: the key I'm in, the relationship of the pitch I'm singing to that key, and the relationship of the pitch I'm singing to the chord I'm playing. Those anchors greatly limit the degree to which I can make a mistake, at least in a simple tonal piece like Desperado that doesn't modulate.
* as I do this, I start noticing that I'm singing grace notes so I make my right hand play those invisible grace notes. It goes alright.
* Now I try singing the corny Sax riff from George Michael's "Never Gonna Dance Again" over the B section-- where the lyrics go, "Don't you draw the queen of of diamonds, boy." The riff actually lines up alright and my hand keeps up.
* Now I try singing some hemiolas and some gospel-type melismas. My hand plays some questionable pitches. I go back and analyze the parts I messed up, trying to figure out where my fingers got tangled up. (Also noticing that I messed up due to singing in a very inaccurate manner.)
* Now I add the left hand. C chord, C chord, C 13, C chord, F chord, F minor in first inversion, 16th octaves descending stepwise from Ab down to E. That creates a doubled 3rd in the chord but the right hand melody leaps away... During this I drop the melismas in the right hand and play the melody straight to keep the harmony shared by both hands moving in realtime. Once I dropped the inner voices (i.e., stopped playing them) and just got the bass in octaves and melody...
When I actually sit down at a piano, I'll be more fluid and accurate at playing Desperado. Because the process I just described away from the instrument is essentially the same process that I follow at the instrument.
Now, if I wanted to add some more interesting chord substitutions and develop something like, say, a gospel style in the inner voices and bass patterns, I'd probably be back where you refer to as "trial and error," working out details without being able to play them in realtime at first. That is to say, most people never gain "fluency" in the sense of just sit down and play anything that you hear with ease. So make sure you're having fun guessing and checking now. Because once you improve to your desired level you'll still have the feeling of guessing and checking with new techniques and sounds.