The interplay of strong interaction and strong disorder, as contained in the Anderson-Hubbard model, is addressed using two non-perturbative numerical methods: the Lanczos algorithm in the grand canonical ensemble at zero temperature and Quantum Monte Carlo. We find distinctive evidence for a zero-energy anomaly which is robust upon variation of doping, disorder and interaction strength. Its similarities to, and differences from, pseudogap formation in other contexts, including perturbative treatments of interactions and disorder, classical theories of localized charges, and in the clean Hubbard model, are discussed.