Is it traditional for native Spanish-speakers to say "Buena suerte," or is it just a traditional English phrase translated into Spanish?
Yes, though somewhat distantly, and it is also related to "sorcery." It comes from Latin sorte, ablative form of sors meaning "fate" or a response from an oracle. Sort comes from Old French sorte, which comes ultimately from Latin sors.
Where I live, I hear mostly mucha suerte. I'm curious this is related to country of origin. Most of our Spanish speakers are from Central America and the Caribbean.