Last time I tried to buy panniers for my push-bike, the shop recommended a backpack instead. I use a smallish one quite a lot. My BOB is a rucksack but somewhat heavier; I've not tried cycling with it yet.

A backpack would make life easier if you had to abandon the bike and proceed on foot.