Typically, they verify eligibility by asking for documentation such as a military ID, a Veterans Affairs card, or other proof of service. It's best to contact the specific carrier you're interested in for their verification process.