Are you using the wireless dongle? Deck doesn't seem to support it by default; when I looked into it, people had to do stuff through the console in order to make the dongle be picked up through the Deck.
I don't have an xbox controller, so I can't endorse what I found as being correct or safe... you have to give whatever it is system access, so be careful and look into it further so that you can make sure that you trust it.
But basically I just searched xbox 360 controller steam deck and reached reddit posts and YT videos covering it. If you decide to proceed, make sure you're using current info, because apparently older methods expired when Steam OS went to 3.5... and maybe they did again going to 3.6, though I didn't see that mentioned. Good luck!
Theres the xbone package you need for that and last time I checked each update wipes it from your system. So good luck, it'll be a constant battle. I just bought wired off brand ones.
Which controller model is it exactly? You don't require any additional software on the deck to connect peripherals via Bluetooth. I've connected even two different generations of Xbox wireless controllers at the same time with my deck without problems.
Are you properly putting the controller into pairing mode when trying to connect?