[Shinyo]

Edit: I wasn't 100% sure of my previous answer so I did some research. I was certain that the the だ and なら were originally grammar particles, so I did a search on 小夜(さよ) and found that it means 'evening.' With this in mind I then concluded that these expressions could have come about when stopping work in rice fields or something to return home when it became dark.

For example:
小夜なら帰ろう。
sayo nara kaerou.
If it's evening, let's go home.

I assume that over time people got lazy and started dropping off the end, which may be how 'sayonara' came about as an expression for 'goodbye'.

That said, I believe the difference between 'sayonara' and 'sayoda' is simply that 'sayoda' is more blunt and less polite than 'sayonara'.