You'll have to pull off all the aluminum trim around the edges first, the linoleum runs under it. It's rivetted down (at least mine was). I had to straighten mine (they bent up during removal), then painted them with silver paint
(gives them that new-sheen again). They were re-installed with wood screws after laying the new floor.
For pulling the floor, use the same method you'd use in a house: putty knife between the linoleum & wood, pulling real hard and sweating a lot. :)
I redid my floor with 1x1 tiles (didn't want the hassles of cutting and laying full-sheet linoleum.) For MOST of the floor I just used the self-adhesive stuff already on the back. For the vertical surfaces though (metal), I had to use additional glue (standard linoleum/vinyl tile glue). The self-adhesive stuff didn't want to stick to the metal. Oh... I also hit those metal surfaces with rustoleum while I was in there. They had some serious surface rust so it pays to deal with these things while you're there.
In retrospect, I'd recommend using the extra glue on all surfaces. It should help fill the gaps between the irregular surface of the wood and the tiles. The self-stick stuff on their backs doesn't do a great job of filling. Haven't had any of my tiles come up, but I'd do it different this time.
If it's just slightly soft - you should consider adding a resin to it to harden it instead of replacing. I did that with a small soft spot (about the size of an old dollar coin (a bit bigger than a toonie for those north of the border)). I didn't want to yank out major sections of flooring for just one small spot. Think: Dentist. drill & fill... :)