I reanimated an old city bike.
The front brakes work fine but the brakes squeaks. So I cleaned the rim and brakes, now the fork shakes on braking.
What is wrong and how can I fix this? Change the brake pads?
What did you clean the pads with? If there is residue left on them, this can cause the stuttering that you speak of. The angle of the pads also matters. You should toe them in so that the front edge hits first, to minimize squeaking.
Another potential problem is a loose headset (as mentioned by a commentor). Grab your stem in one hand and fork in the other. See if there is play by shaking back and forth. If you feel something loose, you may need to adjust your headset.
One more possible reason for your issue is that your pads have not been tightened enough.
Note that usually pads need some time to wear in, and match the rim. Until this happens, you will probably experience sub-optimal braking.
Usually you can get around this by adjusting the toe-in of the brake pads - http://www.parktool.com/blog/repair-help/cantilever-brake-service. If that fails, you can swap in higher quality pads. Usually this works for even cheap brakes and forks.
I had a similar problem that was ultimately down to excessively worn bearings in the front wheel.
I'd tightened them previously but they were beyond their usable life and so there was movement side to side in the wheel hub.
Once the wheel was replaced the problem was eradicated.
Check the wheels for any side to side movement and tighten accordingly, if like me this is no longer possible then look at getting a replacement wheel or rebuilding your existing one with a new hub.