Typically, it should take a few weeks to be approved, but every state has its own procedures for checking Medicaid eligibility.