Just finished getting my 30 day visa on arrival extended and thought I would relay my experience:

Beforehand, since I had heard varying stories about the required documentation, I made (triplicate) copies of:
1) my passport photo/information page
2) the passport page containing my visa on arrival stamp
3) my departure card
4) the receipt for my departure card
5) a dummy booking for a flight from Jakarta to the U.S.

and had passport photos in a mix of sizes (just to be on the safe side).

The office I went to was "Kantor Imigrasi Jakarta Pusat" (Jakarta Main Immigration Office) located at:

Jl. Merpati Blok B12 No. 3
Kemayoran
Jakarta Pusat

but, you may want to print out this map:

http://www.streetdirectory.co.id/ind..._Blok+B+No.+3/

to help your driver find the way. It is on a quiet side street--- but there are still several food vendors on the sidewalk if you get hungry.

I recommend you get there when the office opens at 8 a.m., because the entire place shuts down for lunch at noon-- and if you're midway through the process, you wait. Also, if you don't get through the process by the end of the day, you have to come back later to pick up your passport (and this place can be over an hour away from the "Golden Triangle" in heavy traffic).

When you first walk in, you may be confronted by teeming hordes, long lines and a guy making announcements in Bahasa over a microphone-- don't panic, this isn't for you. Instead, you go the the 3rd floor (which is confusingly named the 4th floor), by taking a staircase to your right when you enter. Just to confirm, there is a friendly guy sitting at a "Customer Care" desk just inside the front door who can point the stairway out to you.

After walking upstairs, you want to stop at the 1st window to your left (a small office with a copy machine), the sign there says something like "copi." You will need to purchase two forms:
1) an application for extension 10,000Rp; and
2) a sponsor letter (tell the woman you want to "self sponsor") for 5,000Rp.

Also, if you hadn't made copies all ready, then you will need to pay for copies of your passport information page and visa stamp page from your passport (these are 500Rp each). I was also asked for passport photos (which I luckily had, none of the posts I had previously read mentioned a need for those).

The application is straightforward (1 page) and in English. The sponsor letter is in Bahasa, but all you need to do is fill in your name, passport number, nationality, date, and sign across the stamp (she will show you where to put each item-- it's pretty simple).

In addition, she will give you a bright red official folder-- this will hold your documents.

Fill out the two forms, place the copy of your passport info page and visa stamp behind them, then take them along with your passport and your photos to the counter next to the wooden desks (past the ping-pong table-- really!). After handing these over, you will be told to have a seat and wait.

After awhile, they call you up to collect your folder-- now you have to take it to the counter over your right shoulder. After handing the folder over, you will be told to have a seat and wait.

After awhile, they call you up to collect your folder-- now you have to take it to the next counter over to your right. After handing the folder over, you will be told to have a seat and wait.

After awhile, they call you up to collect your folder-- now you have to take it back to the counter which will now be over your left shoulder (this is the one next to the wooden desks). After handing the folder over, you will be told to have a seat and wait.

After awhile, they call you over and give you an invoice for 250,000Rp. You have to take this invoice down to the cashier on the ground floor. The cashier counter is located at the window closest to the stairwell and is a kind of glass-walled small room with a guy collecting money in an overflowing box and yelling into a microphone. Give him the invoice and the money. He throws the money in the box then hands the receipt to a over to a woman on his right who prints out the receipt. Try to make eye contact with her so you will know when your receipt has printed and she will give it to you through a small window so you don't have to deal with microphone/money box guy (who usually has a lot of people kind of anxiously crowded around his window).

Now, take the receipt back up to the guy on the 4th floor. After handing the receipt over, you will be told to have a seat and wait.

After awhile, he will call you over, give you your passport and direct you to the counter where you bought your forms to get a copy made of the extension stamp. This will cost 500Rp. (I'm not sure what would happen if you just skipped this step and made a run for it with your passport, since it now has the extension stamp in place).

After this, take the copy back to the guy. He will now tell you you're done.

The entire process took me about 1 and 1/2 hours and was actually kind of interesting. For the most part, the people were nice, and did a good job pointing me to the next step in the process (there was a flow chart on the wall that attempts to explain the steps, but it is in Bahasa, contains a circular loop and seemed to indicate at least one step that ends at a dead end). The floor on which all of this takes place (except the cashier) is pretty quiet and there were never any lines at any of the windows.

Since the building sits in a quiet area, you may have to walk a bit upon leaving to find a taxi-- I happened to stumble upon one cruising the back streets after about 3 minutes, so I didn't have to go walk all the way to the main road.

Hope this helps.