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'.
By the way, do you have any idea where my mackintosh is? I've looked everywhere.
By the way, I expect my bike back or somebody's photo is about to get destroyed.
By the way, I need my pen back.
On a side note, I've found my mackintosh.
On a side note, can I borrow your bike?
On a side note, do you have any idea when the party is?
On a side note, can I have a bite of that chocolate cake? It looks awfully good.