It is possible to upgrade the CPU to a Pentium M Dothan core. Also just so you know the Celeron M that you have is based on a Dothan core however the Celeron M processors have half of their cache permanatly disabled in hardware (no it can't be re-enabled). The Celeron M's also have the speedstep hardware permanantly disabled so the processor always runs at full power thus killing your battery life.
That being said I must warn you changing the processor in a laptop is not like a desktop. You would have to take apart most of the laptop to get to the processor which can be very tricky. It is very easy to break/damage things doing this. I would say if you don't know what you are doing and don't have the money for a replacement laptop than don't try it.
As for RAM, you should definatly get at least antother 256 MB and idealy you should toss your 256 stick and get 2 x 512 MB sticks for a total of 1 Gig. There is no reason why simply adding a 512 MB to your 256 MB won't work however. You save a little $ and still have 768 MB. Adding more RAM will make a HUGE difference in this system and I might even go so far as to guess that after upgrading your RAM you may not feel the need to worry about the processor any more. Upgrading the RAM is easy as there is an easy access cover on the bottom of the laptop, just one screw.