When using bitcoin-cli I get an error regarding fallback fees when trying to send regtest Bitcoin. How do I resolve this?

You can set the fee rate easily when using named parameters:

bitcoin-cli -regtest -named sendtoaddress 
  address=bcrt1qd3jck0lv87yuk25tk3xy5rqq67apwasee874xk 
  amount=25 
  fee_rate=100

You could enable -fallbackfee (as darosior says) but the easiest or quickest way to resolve this is to set a fee. In this example we are setting a fee of 1 satoshis per byte.

./bitcoin-cli sendtoaddress "bc1q09vm5lfy0j5reeulh4x5752q25uqqvz34hufdl" 0.1 "" "" false true 1 sat/B

If you do

./bitcoin-cli -regtest help sendtoaddress

you will see what those arguments after the regtest address represent.

Alternatively if you want to set the fallback fee see this StackExchange question.

This PR 16524 merged in October 2019 disabled -fallbackfee across all chains (mainnet, testnet, regtest) by default.

bitcoind uses transactions it relays (and later see as mined) to estimate the feerate to set for transactions its wallet creates.

On regtest, you don't relay then mine enough transactions so bitcoind's estimation buckets are not filled enough to give a reliable estimate. Without such an estimate the wallet, out of safety, prefer not to create any transaction unless you explicitly tell it what fee to use when fee estimation isn't available.

This "fall back feerate" can be set up at bitcoind's startup with the fallbackfee startup option, expressed in BTC/kB.

   -fallbackfee=<amt>

         A fee rate (in BTC/kB) that will be used when fee estimation has
         insufficient data. 0 to entirely disable  the  fallbackfee  fea‐
         ture.  (default: 0.00)

Alternatively, crafting transactions on different nodes of your regtest network and getting them mined will result in estimation buckets to be filled.