'Soft' iron meaning 'magnetically soft' (low coercivity and retentivity) also happens to be physically soft. That is where the term 'soft' originates. This applies only to iron and steel; ferrites can be magnetically 'soft' or 'hard' but are always physically hard.
Sot iron ( also called magnet steel or 'commercially pure' iron) as used in magnetics is very low carbon-content steel, less than 0.05%. It can be ordered from industrial suppliers but may require minimum quantities and thus be expensive.
A good substitute is mild steel: with % C ranging from 0.06 (AISI 1006) to 0.3 (1030). Most-commonly encountered are 1010 (0.1% C) and 1020 (0.2%). Machine key stock, the zinc-plated stuff from your local hardware or home center, is generally of those grades. So are SAE Grade 2 bolts (also zinc-plated).
Structural steel (not concrete rebar, which being made from scrap can have wildly-varying carbon content) of mill (plain) finish, in plate or square bar form, typically used for decorative metalwork, can be obtained from the same sources or from junkyards. It is generally higher-carbon than mild steel, but can be made magnetically (as well as physically) soft by annealing. This is done by uniformly heating to cherry-red (about 1500 F), and allowing it to cool slowly. (Quick cooling--quenching--hardens steels of medium and high carbon content both physically and magnetically, which is good for permanent magnets, but the opposite of what you want.)
As others have mentioned, transformer and induction-motor cores are made of laminations of magnetically-soft steel of low carbon but high silicon content (the latter to increase resistivity thus reducing eddy-current losses) and are good when AC is involved (but work fine for DC too). These can be obtained cheaply from scrapyards as well.