How do wallets select which balances get sent as part of a transaction? I'm a newbie at this and still trying to get my head around Bitcoin. Three linked questions around how the transaction works...

1) How does the wallet decide which balances/addresses form part of a new payment transaction (to go as the input)?

2) Do all transactions generate 'change' - i.e. a second output?

3) Does the fee for a transaction go to a newly generated miner's Bitcoin address, a pre-recorded miner's address, or is there no output in the blockchain associated with this?

Thanks and apologies for technical inaccuracies and silly questions.
The standard software uses some heuristics trying to minimize the transaction data size (which mostly means as few inputs as possible), with preference to older outputs which have higher priority. More information is available at What is the coin selection algorithm? and https://en.bitcoin.it/wiki/User:Gmaxwell/coin_selection.
If the sum of the inputs you use is larger than the amount of coins you wish to send, and you want to get the difference back rather than paying to the miner, you'll need a change output. Since the inputs almost never happen to sum up exactly, and you do want the change, almost all transactions have a change output; but there's no rule saying there must be one.
Every block has a special generation transaction. The miner who finds the block can freely choose the outputs for this transaction, as long as their total value is no more than the generated coins + total transaction fee.