How do we buy storage without a credit card

With a gift card:

iCloud storage plans and pricing - https://support.apple.com/HT201238

"Accepted payment methods for iCloud storage upgrades include credit cards, debit cards, and iTunes Store credit."

Create or use your Apple ID without a payment method - https://support.apple.com/HT204034 - "When you use your Apple ID to sign in to the iTunes Store, App Store, or iBooks Store for the first time, you're asked to enter a payment method so that you can purchase items from the store. Follow these steps if you don't want to associate a payment method with your account." -

But:

If you can't remove your last payment method or use no payment method with your Apple ID

[formerly: If you can‘t choose None when you edit your Apple ID payment information]

"Learn why you can't use your Apple ID without a payment method in the App Store, iTunes Store, and more." - https://support.apple.com/HT203905 - also make sure you don't have any active subscriptions, are set as the Family Organizer for a Family Sharing plan, or owe any money for past purchases.

A storage upgrade is an active subscription and requires a payment method, though as long as you have credit in your account from gift cards that payment method won't be used.