I would also say " We're going on holiday to Italy." But I saw the following sentence in a Longman Dictionary " We used to go on holiday in Scotland when we were kids."
It seems rather old-fashioned to me - it's not how I would say it. I would tend to say "We used to go on holiday to Scotland" or (if I were being formal and trying to sound posh) "We used to holiday in Scotland".