Increasing oxidation state is the same as saying becoming more oxidized. Think of oxidation as an atom increasing the amount of bonds towards oxygen. Therefore, as we increase bonds towards oxygen (increasing oxidation, increasing oxidation state), the electron density changes significantly.
Think of HNO2 (Ka 5 x 10 ^ -4). If the nitrogen atom increases it's oxidation state, it becomes HNO3 (Ka 28). The nitrogen atom's oxidation state increased, changing the electronegativity of the molecule making it more acidic.
Hope this helps! Let me know if you're still confused.
Think of Lewis acidity and basicity. This is the easiest concept to use to visualize this question. What is Lewis acidity? It's the tendency for atoms to accept electrons. On the other hand, Lewis basicity measures the tendency of atoms/molecules to donate electrons. So what happens as oxidation state increases? For instance, compare Fe3+ (ferric) to Fe2+ (ferrous). Which would you expect to want electrons more? Probably the one with the higher oxidation state - it's had more electrons taken from it, so it's more "electron starved." Also, if you look at the simple ionic forms, ferric has a +3 charge whereas ferrous has a +2 charge. You'd expect the more positively charged one to want electrons more. Wanting electrons more = more willing to accept electrons = better Lewis acid.