What's the difference between "on a side note" and "by the way"? Is one of them restricted to certain situations while the other is not?
By the way may bring up a new major topic — related to the previous one. You may shift the whole conversation into a new direction, and keep it on that new topic for a while, drilling it thoroughly.
On a side note should be just a small side note — similarly you shift the subject somewhat, but you just drop a small bit of information and you're either back to the previous topic or ending the conversation.
Other than that, you'll see the two in somewhat different contexts. You'll rarely hear someone asking a question "on a side note", while "and by the way, did you...?" style questions are very common. "By the way" is more informal, commonly appearing in day-to-day speech, while "on a side note" would be something to be seen more in more formal contexts.
I have never come across 'on a side note'.
I think 'incidentally' is a good word to use for an aside.
During a conversation between two lawyers, let's say about someone's willingness to give evidence in court, one of them might say: 'Did you know, incidentally, that he has a criminal record?'.
Or with a doctor, when discussing feeling unwell, 'I have, incidentally, just returned from a journey up the Amazon in a rowing boat'.