If driving, you will certainly need to have Omani travel insurance. If you're hiring the car, you can ask for this when you hire it (worth doing to save the extra delays at the border).

Generally the process is:
1) Reach UAE border, get out, queue to stamp out of the country and if you own the car, pay a "fee" to allow you to take it out of the country once you have proved that you own it (show your registration card - in hire cars this is usually a photocopy in the glove compartment).
2) Reach Omani border, join melee to get Omani entry visa.

If you are not alone, I would highly recommend that one of you jumps out and gets in the queue while the other parks the car at both border points. It is also quite possible to drive through the border without the stamp: the border guard will ask you to park immediately on the other side then walk back through to stamp in/out. If you do things this way, once you're stamped you don't need to queue to leave the country - as physically your car is already through.