It's a slightly awkward phrase, because it's mixing different Englishes - 'seaside' is British English, while 'vacation' is American. In British English, you might say 'They often go on holiday to the seaside'. Or if you want to use 'for' - indicating purpose/reason - you might say 'They often go to the seaside for a holiday' or 'They often go the seaside for their holidays'. Note that 'on holiday' is a fixed phrase - like 'at school' or 'at work' - so there is no article. If you use any other preposition, you need an article. I'll leave it to a speaker of American English to suggest a suitable expression with 'on vacation.'

They often go to the beach (not seaside, in AE) for vacation. "On vacation" ------ The Smiths aren't home, they're on vacation.

They often go to the seaside for vacations. ( because "often" means "many" thus "vacations") If you decide to use ON. Then a better phrasing would be, They will often go to the seaside on a vacation. I personally prefer, They will often go for vacations by the seaside.