It isn't a double negative, although it is a bit of an usual phrasing.
The context that you are overlooking is that the United States Constitution does not say who is or is not allowed to vote because that authority is not vested in the federal government. There is no affirmative right to vote in the United States Constitution, there is merely a right not to be denied the right to vote for certain particular reasons.
Responsibility for determining who is allowed to vote is vested in state governments. The right to vote for the House of Representatives is derivative of that decision pursuant to Article I, Section 2, Clause 1 of the United States Constitution which states:
The House of Representatives shall be composed of Members chosen every
second Year by the People of the several States, and the Electors in
each State shall have the Qualifications requisite for Electors of the
most numerous Branch of the State Legislature.
The 19th Amendment prohibits state's from denying the right to vote on account of sex, but does not prohibit states from denying the right to vote on account of other grounds not specified in the 19th Amendment, such as property ownership, education, criminal record, possession of identification, etc.
When the 19th Amendment was ratified, in 1920, some states (e.g. Colorado) already allowed women to vote, while others did not. Similarly, when the 15th Amendment was ratified some states prevented people from voting based upon race and others did not. And, so on.
In practice, the modern trend is for states to enact laws allowing all U.S. citizens age eighteen or over to vote, subject primarily to limitations that vary quite a bit based upon criminal record or incarceration status. But, historically, when the power to set the franchise was vested in the states, race, gender, property ownership, age (in excess of eighteen), poll tax payments, and "civics" tests, have all been used at sometime or another to limit the right to vote.
There is, however, some incentive for states not to be restrictive, because certain kinds of restrictions reduce the population of the state under the U.S. Constitution for purposes of allocated members of Congress and electoral votes. This is set forth in Section 2 of the 14th Amendment to the United States Constitution (ratified in 1868) which states:
Representatives shall be apportioned among the several States
according to their respective numbers, counting the whole number of
persons in each State, excluding Indians not taxed. But when the right
to vote at any election for the choice of electors for President and
Vice President of the United States, Representatives in Congress, the
Executive and Judicial officers of a State, or the members of the
Legislature thereof, is denied to any of the male inhabitants of such
State, being twenty-one years of age, and citizens of the United
States, or in any way abridged, except for participation in rebellion,
or other crime, the basis of representation therein shall be reduced
in the proportion which the number of such male citizens shall bear to
the whole number of male citizens twenty-one years of age in such
(Incidentally, there are no longer any people who qualify as "Indians not taxed" in the U.S. due to federal legislation that was adopted after 1868.)
This set a presumptive baseline that males twenty-one years of age not disqualified by a criminal record are allowed to vote, but with a penalty for not doing so imposed at the state level in apportionment rather than in the form of a prohibition against doing so, before express prohibitions against certain kinds of restrictions of the franchise were adopted in the 15th, 19th, 24th and 26th Amendments.
It is also useful to compare the examples of the 15th Amendment (ratified 1870), the 24th Amendment (ratified 1964) and the 26th Amendment (ratified 1971), which are parallel to the 19th Amendment and wouldn't make sense against a backdrop that the population, by default, is allowed to vote.
Article XV (Amendment 15 - Rights of Citizens to Vote)
The right of citizens of the United States to vote shall not be denied
or abridged by the United States or by any State on account of race,
color, or previous condition of servitude.
The Congress shall have power to enforce this article by appropriate
Amendment XXIV (Amendment 24 - Abolition of the Poll Tax Qualification
in Federal Elections)
The right of citizens of the United States to vote in any primary or other election for President or Vice President, for electors for
President or Vice President, or for Senator or Representative in
Congress, shall not be denied or abridged by the United States or any
state by reason of failure to pay any poll tax or other tax.
The Congress shall have power to enforce this article by appropriate legislation.
Amendment XXVI (Amendment 26 - Reduction of Voting Age Qualification)
1: The right of citizens of the United States, who are 18 years of age
or older, to vote, shall not be denied or abridged by the United
States or any state on account of age. affects 15
2: The Congress shall have the power to enforce this article by