That mega-isp was brillitant! 
A big thanks to the folks behind mega-isp! Great work!
I have some extra atmega 328's that was empty with exactly this in mind.
Some problems though, avdude reports that the programmer is out of sync sometimes, quite often in fact. I don't know why that is, it generally means I can't verify. Eventually I chosed to ignore the error, and it seems to work - they can upload and run sketches from the arduino IDE Which is what I wanted of course, I like that IDE. But I guess I can do (almost) without it now, but I'll wait with that until I need the space and get some more experience.
I'm really quite new to this, so the first tries didn't went too well. Until I read about the fuse settings. I followed the settings listed here: http://blog.modifiedelectronics.com/2009/08/arduino-atmega328-fuse-settings.html and (sort of) verified them against the fuse calculator here AVR® Fuse Calculator – The Engbedded Blog
I used the ADABOOT bootloader btw, since that's what was shipped on my BBB - Bare Bones Board (Arduino compatible). And more important - it seems to be a very good bootloader. http://www.wulfden.org/TheShoppe/freeduino/ADABOOT.shtml
I'm not sure why the hex file is 6k, but the bootloader 2k. I guess there are other stuff in it as well, probably including the (hex) adresses of the contents?
The fuse settings for an Atmega 328 with a 2kB (1k word) bootloader is, or at least can be (though no guaranties, of course):
High: 0xDA
Low: 0xFF
Extended: 0xFD
Oh yeah, I almost forgot the lock-bits.. in fact I tested the atmega's in the Arduino IDE before settings these, but it sems to work even though I programmed these afterwards (I just used a simple blinker app to test from the Arduino IDE anyway, no fancy stuff like interrupts or program memory access).
I set the lockbits (according to the same blog) to be 0xCF. Checking the settings in the Atmega 328 datasheet seems to indicate it is safe, but I'm no expert (table 25-1 and 25-2 page 294).
Reading back (verifying) the extended fuse setting seems to be inverted, so there is an error about it being changed. Same thing with the lock bits, but that one seems to just be the upper nibble inverted (or ignored?). Ignoring these errors seems to work (as long as the device ID checks out).