Are most things generally discovered because they work empirically and later justified mathematically, or vice-versa?
There are definitely approaches that are theory driven (like SVMs), and others where the theory comes after the practice (like a lot of deep neural networks). I think it would be difficult to argue strongly that either direction is more common "in general" within AI, or indeed, within any other branch of science. 

The approach that is currently in favor will tend to change over time as well. If we develop a new method that we don't understand, it will tend to attract interest from theorists. If they are able to understand it well, that understanding will likely lead to natural next steps that improve the model. As with other areas of science, the empirical cycle is at work.