トリガーの設定を何度やってもビルドが始まらず、なんでろうと思っていたのですが、Webhookの設定がされていないことが原因でした...
最初のアプリのセットアップでWebhookの設定の工程を飛ばしてしまっていたようです。
Bitriseでアプリを選択し、Codeタブを開くと下の方にINCOMING WEBHOOKSの項目があります。
SETUP AUTOMATICALLYをクリックすると一瞬で設定が完了します。
Github側にもWebhookの設定が反映されていることが確認できました。
この状態でブランチをプッシュしたら無事にビルドがトリガーされるようになりました。