There are many possibilities:
You could use a transformer (like the transformer from a flash light) to get the 500V at once.
You could use a more normal transformer with a diode cascade.
Some use only an inductance with a diode cascade.
Some use a feedback with zener diodes.
You could read the voltage with the Arduino, but the voltage divider will draw some current, even if the resistor for high voltage is 2 * 22M.
You coulde use the Arduino to generate a signal for the transformer.
Take a look at the schematic of this one : https://www.sparkfun.com/products/10742
It uses a normal audio transformer and a diode cascade.
These projects are helpful : http://hackaday.com/tag/geiger/
This one is also with full schematic (click on design files) : http://mightyohm.com/blog/products/geiger-counter/
I had some trouble to reach a high voltage for my Geiger tube. So I tried to find the resonance frequency of the transformer (flash light transformer). It was between 40kHz and 50kHz, and suddenly I could reach 900V. I read the voltage with the Arduino via 2 * 22M, and I adjust the frequency of the transformer driver (using BC547/BC557). But my circuit is specific for that transformer.
Which Geiger tube do you have ? I hope not the CI-3BG (also called SI3GB, SI38G, etc), they are not sensitive.