What does it mean that the early supreme court "gave themselves" the power of judicial review?

Your description accurate enough. The US Constitution is a broad document and does not have paragraphs for every little action that the government does. It set up the Supreme Court, to have jurisdiction over all law cases appealed to them. When Marshall first used Judicial Review, it 'made sense' that if anyone were to decide that a Federal Law violated parts of the Constitution, then the Supreme Court would be the place to decide.

Enforcement is done by the same Legislature that was overruled, because they now accept this power as a good thing in the balance. When the Supreme Court makes a blockhead decision the Legislature might decide that it will not do so, or trump the decision by extending the Constitution.

Both these were done for the Dred Scott, where a Southern dominated Court tried to 'fix' sectional controversy by claiming that Blacks, free or slave, could never be US Citizens among its many claims. The Republican party vowed not to enforce this, and when in power during the Civil War added amendments that made both Slavery and this decision a dead letter.

It is the responsibility of a court to determine what the meaning of a law is, in other words to interpret the law. It follows from this that if laws are inconsistent or incompatible then the court may void the law. This is true not only of the Supreme Court, but of any court. In essence the courts have the ability to veto any law which is invalid. A law can be invalid if it is self-contradictory or is inconsistent with other pre-existing laws.

In the case of the Supreme Court, they may hold that a law is inconsistent with the Constitution, in which case the law is voided irrevocably. The difference between the Supreme Court and lesser courts is that if a lower court decides that a law is unconstitutional it can be overruled by a higher court, but the Supreme Court's decision cannot be appealed.

Some of the basis for judicial review is almost tautological. In order for judges to issue decisions consistent with the law, the judges must know what the law is. If a case arises where the existing laws do not clearly say which side should win and which side should lose, a judge may have to make a decision based upon factors beyond those specified in the law. Again, this is almost tautological: if X must be done (someone must be awarded the win), but Y is insufficient to do X (the law is insufficient to determine who that should be), then X must be done by some means beyond Y (judges must used something other than the law as written in making their decisions). Although it's not entirely tautological, it should generally be non-controversial that when a judge takes into consideration factors other than the law as written, it is better for him to document how a decision was reached, than to allow judges to make arbitrary decisions without justification. Further, people who know how the judge will interpret ambiguous laws will be better able to avoid being unpleasantly surprised if similar cases arise in future and the judge rules the same way.

The point where things become problematic is when one progresses from "part of a judge's job is to say what a law means" to "the law means whatever a judge says it does". If a judge is properly doing his job, he will say what the law means and thus the law will mean what he says. On the other hand, the two statements above will only be equivalent as long as a judge never says anything inconsistent with what the law says. If a judge makes a ruling inconsistent with the law, the ruling won't change the meaning of the law. Rather, it will indicate an expressed intention to illegitimately ignore the law in future similar cases.

Over the years, the presumption that those in power (be they judges or whoever else) should do their job has unfortunately evolved into an unassailable axiomatic belief that they will, to the extent that causal relationships have reversed, and people perceive the court's actions as making things constitutional or unconstitutional, rather than being consequences of whether the things actually were constitutional or not. If one reads decisions like Marbury v. Madison with the view that the court is following the law, it will be consistent with that view. If one reads them with the view that the court is shaping the law, it will also be consistent with that view. Consequentially, the decisions may have been "accepted" [allowed to exist without provoking immediate reaction] because people interpreted them the former way; then at a later time, those pushing the latter viewpoint could use the existence of the earlier decisions to imply that their viewpoint represents the way things have always been.

@Oldcat has the core of the answer. Judicial review was not part of the constitution. The constitution says very little about the judicial branch beyond the assertion that we should have one and the implication that it should be independent of the legislative and executive branch. The constitution mandates only one court, and doesn't say anything about how many justices, how often it will sit, how the justices will be chosen, how long they will serve.

The Democratic Republican Party was deeply hostile to the judicary - they felt that only republican citizens could decide facts and concepts like precedent and law would diminish the republican virtues. (My source is long buried, but I believe that any biography of Jefferson or the election of 1800 will expand on this).

Since the constitution is silent, a strict and literal review of the constitution would therefore contend that judicial review is a power reserved to the states or the people. That would have resulted in disaster. Even when the constitution was being debated, almost nobody was arguing for the chaos of the articles of confederation. Everyone recognized that the national government had to be slightly more powerful than the states, or we would return to that disaster.

Marshall was a canny politician and recognized that Marbury Vs Madison was an opportunity to solve a problem. He invented judicial review and both sides have kept it/respected it because it solves that problem. If the Supreme Court's interpretation is at odds with the legislative intent, then Congress can redress the problem. If the interpretation is unenforceable, then the executive branch will ignore it. But the critical thing is that the decision is made, is made in a relatively disinterested fashion, and is made in a way which is relatively final.

If you really want to understand why the power of judicial review has survived, try to design a system where the power of judicial review is absent, and there is a conflict in the interpretation of fundamental precepts of law. That is the core problem, and it has to be solved. Marshall's solution was elegant enough that it has survived.

Also recognize that it is entirely possible that they hadn't anticipated the problem of judicial review. The US constitution broke novel ground and created problems that hadn't existed before. I haven't seen any evidence that anyone had raised the problem in any of the constitutional conventions. (I'm open to counter-evidence).

Remember that British courts work on British common law, which treats prior precedent as binding, but all interpretation is done by judges who serve at the pleasure of the King. (at the time). (Also recognize that many of the judges at the time are not trained in law; they serve as members of the aristocracy. The USA didn't acknowledge their aristocracy, and the zealot republican faction opposed the aristocracy.) So there are two fundamental reasons why the USA cannot simply adopt the British system.

I don't have enough insight into French Judicial practice at the time, but I believe that the USA could not solve the problem that way either - French authority emerges from and ends with the King, and that was not a legitimate solution for the early USA.

We respect judicial review because it solved a problem in a way that didn't gore anyone's ox too badly, because the people who were offended by Marshall's powergrab were on the decline, because Marshall was very well connected and politically skilled, and because the government is stronger with it than with any alternative that has been proposed.

The constitution is flexible enough that we could have replaced it with something else if we'd needed to. After all we added the income tax, Executive Orders, the military industrial complex and the welfare state. But nobody has proposed any (realistic) alternative.

It is in the Constitution - implicitly. The it "isn't anywhere in the constitution" argument is frequently popular to different groups on different topics, but in this case at least has no legal basis in jurisprudence.

The judicial Power of the United States, shall be vested in one supreme Court ... The judicial Power shall extend to all Cases, in Law and Equity, arising under this Constitution, the Laws of the United States, and Treaties made, or which shall be made, under their Authority;

_{-- Article III of the United States Constitution}

In Article Six, the Constitution asserted itself to be the supreme law. This meant that any law that contradicts the Constitution weren't valid - and the power of determining whether that was the case falls to the Supreme Court. In this way the Constitution intentionally (see below) provided for the judicial review of United States laws by the Supreme Court.

That a Constitutional power is not literally spelt out, does not make it any less official.

Based on your comments, it seems your question is why people accepted the Supreme Court wielding this power. Apart from what @Oldcat has said about it being generally thought of as a good idea, another reason is that this was established legal doctrine.

That is, judicial review was not something Marshall's Supreme Court "just decided to do". Remember, United States law did not appear out of a vacuum. It is a direct continuation of English common law as it existed in the Thirteen Colonies. All laws and jurisprudence continued to be in effect after independence, unless otherwise repealed. The relevance here is that judicial review had been previously raised in English common law:

And it appeareth in our Books, that in many Cases, the Common Law doth controll Acts of Parliament, and somtimes shall adjudge them to be void: for when an Act of Parliament is against Common right and reason, or repugnant, or impossible to be performed, the Common Law will controll it, and adjudge such Act to be void ... for the arrearages incurred in the life of the auncestor do not belong to the heir: and because it shall be against right and reason, the Common Law shall adjudge the said Act of Parliament as to that point void

_{-- Thomas Bonham v College of Physicians, 77 Eng. Rep. 638 (1610)}

In his landmark judgement, the Rt. Hon. Sir Edward Coke drew upon a history of cases and declared that Acts of Parliament might be voided. Under what circumstances this might take place is debated; it seems that at the very least he meant laws that were clearly repugnant could be set aside, but more generous interpretations argue Parliament could not contradict existing common law.

Regardless of which he originally meant, Lord Coke's judgement helped establish the concept of judges voiding invalid laws. Within England, what makes a law invalid was debatable due to the lack of a formal Constitution. While repudiating a law that's repugnant to natural rights might be supportable, Parliament obviously should be able to override normal common laws. This eventually meant Parliamentary Sovereignty became established doctrine after 1688.

In the Thirteen Colonies, moreover, it was an established principle that colonial legislation repugnant to the laws of England were void ab initio. Judicial review of colonial laws in English courts was thus very much an active process prior to the Revolutionary War. A number of colonial legislation were thus viewed by the Privy Council, and at least one, a 1699 Connecticut Intestacy Statute, was declared null and void in 1728.

After 1776, the principle persisted in the states, reasoning that state constitutions ought to be applied before regular state laws. Thus, the concept of judicial review, already well established in the common law of the colonies, informed both the drafting of the Constitution as well as the operations of the Supreme Court thereafter. It would have been assumed that judges would simply continue doing what they've been doing all along, and invalidate any law that's repugnant to the Constitution.

In summary, Marshall's Supreme Court did not "gave themselves" a new power. They applied a widely understood and accepted legal doctrine. In fact the early Supreme Court actually conducted judicial reviews in a number of cases prior to the landmark Marbury v Madison. There has been records of at least dozens of cases of judicial review, both by the Supreme Court and on local/state levels, before the 1803 case.

(The below section was originally posted separately since a moderator decided to lock this answer, preventing me from defending my arguments to Vector & Co. I've decided to merge its contents back, with some edits, to avoid having two answers to the same question.)

Addendum: Evidence for the Existence of Judicial Review

Some commentators assert that my answer is wrong because mysteriously nameless "historians" disagree with me. Despite their persuasive credentials of having taken a history class in high school, however, the existence of judicial review as an element of then-extant judicial powers is very well attested to by primary sources from the period.

Framing of the Constitution

Arguably @MarkCWallace was correct in saying judicial review was not "discussed" ("The power is not in the constitution, and was not, to the best of my knowledge, discussed in the formation of the constitution") in the Constitutional Convention. However, that would be misleading. It was not "discussed" because it was universally, or near universally, agreed to be a judicial power. With no dissent there, was no reason to debate. People do not discuss the sun's rising from the east either, and that is not evidence that some thought it rises from the west.

In fact, the framers of the Constitution mentioned judicial review several times, especially in relation to an executive veto. Unlike the executive veto, which was debated as a proposal, judicial review was assumed to be already assigned to the judiciary.

Mr. King was of opinion that the Judicial ought not to join in the negative of a Law, because the Judges will have the expounding of those Laws when they come before them; and they will no doubt stop the operation of such as shall appear repugnant to the constitution.

_{-- Notes of Major William Pierce on the Federal Convention, May 1787}

Mr. GERRY doubts whether the Judiciary ought to form a part of it, as they will have a sufficient check agst. encroachments on their own department by their exposition of the laws, which involved a power of deciding on their Constitutionality. In some States the Judges had actually set aside laws as being agst. the Constitution. This was done too with general approbation. It was quite foreign from the nature of ye. office to make them judges of the policy of public measures.

_{- James Madison's Notes of Debates in the Federal Convention, June 4, 1787}

Mr. Govr. MORRIS was more & more opposed to the negative. The proposal of it would disgust all the States. A law that ought to be negatived will be set aside in the Judiciary departmt. and if that security should fail; may be repealed by a Nationl. law.

_{-- James Madison's Notes of Debates in the Federal Convention, July 17, 1787}

As the notes show, the idea of the judiciary exercising the power of judicial review was so natural to the delegates, that they simply assumed it will be included in the as-yet unwritten Constitution. Rufus King plainly stated that judges will strike down unconstitutional laws. Elbridge Gerry even cited this happening (testifying to the fact that judicial review was an established operation, as I discussed earlier). Gouverneur Morris stands out from the other two by not even limiting the exercise of this judicial power by the confines of the constitution.

On 21 July, James Wilson reintroduced a proposal to link the judiciary to the executive for approving Congressional legislation. This sparked in the most extensive debate on this subject in the convention. As the delegates argued over the wisdom of having judges review legislation (as opposed to waiting for cases to review the law), both those who were for and against the proposal mentioned judicial review.

Mr. WILSON ... It had been said that the Judges, as expositors of the Laws would have an opportunity of defending their constitutional rights. There was weight in this observation; but this power of the Judges did not go far enough. Laws may be unjust, may be unwise, may be dangerous, may be destructive; and yet may not be so unconstitutional as to justify the Judges in refusing to give them effect.

Mr. L. MARTIN. ... A knowledge of Mankind, and of Legislative affairs cannot be presumed to belong in a higher degree to the Judges than to the Legislature. And as to the Constitutionality of laws, that point will come before the Judges in their proper official character. In this character they have a negative on the laws. Join them with the Executive in the Revision and they will have a double negative.

Col. MASON Observed that ... It had been said that if the Judges were joined in this check on the laws, they would have a double negative, since in their expository capacity of Judges they would have one negative. He would reply that in this capacity they could impede in one case only, the operation of laws. They could declare an unconstitutional law void. But with regard to every law however unjust oppressive or pernicious, which did not come plainly under this description, they would be under the necessity as Judges to give it a free course.

_{-- James Madison's Notes of Debates in the Federal Convention, July 21, 1787}

What is notable is that neither side deny or even question the power of judges to void unconstitutional laws in courts. This is despite the topic at hand being whether judges should have a say in the making of said laws. Indeed, Luther Martin outright claimed veto powers for the Supreme Court, limited only by needing the law brought before them. It fell to James Wilson and Colonel George Mason to point out judges could only void unconstitutional laws, and not all bad laws might be unconstitutional.

On July 23, the convention briefly considered the matter of how the Constitution was to be adopted. Judicial review was brought up as a potential obstacle.

Mr. Govr. MORRIS considered ... [i]f the Confederation is to be pursued ... Legislative alterations not conformable to the federal compact, would clearly not be valid. The Judges would consider them as null & void. Whereas in case of an appeal to the people of the U. S., the supreme authority, the federal compact may be altered by a majority of them.

Mr. MADISON .. considered the difference between a system founded on the Legislatures only, and one founded on the people, to be the true difference between a league or treaty, and a Constitution. ... In point of political operation, there were two important distinctions in favor of the latter. 1. [FN12] A law violating a treaty ratified by a pre-existing law, might be respected by the Judges as a law, though an unwise or perfidious one. A law violating a constitution established by the people themselves, would be considered by the Judges as null & void.

_{-- James Madison's Notes of Debates in the Federal Convention, July 23, 1787}

Gouverneur Morris pointed out that judges could well void the proposed Constitution for not adhering to the Articles of Confederation's mandated alteration procedures requiring the consent of every legislature. This view was shared by James Madison. But neither challenged judges over the power of judicial review; instead, both argued that if the people supported the constitution then the judges would not object. It is difficult to imagine that no one would speak out against judicial review, if it was not already understood by all to be an established legal doctrine.

In fact, the closest the Philadelphia Convention came to rejecting the doctrine of judicial review, actually helps established what I have written earlier: that the concept of judicial review was a legal doctrine established by then.

Mr. MERCER heartily approved the motion. It is an axiom that the Judiciary ought to be separate from the Legislative: but equally so that it ought to be independent of that department. ... He disapproved of the Doctrine that the Judges as expositors of the Constitution should have authority to declare a law void. He thought laws ought to be well and cautiously made, and then to be uncontroulable.

_{- James Madison's Notes of Debates in the Federal Convention, August 15, 1787}

The disapproval of John Francis Mercer was shared by John Dickinson.

Mr. DICKENSON was strongly impressed with the remark of Mr. Mercer as to the power of the Judges to set aside the law. He thought no such power ought to exist. He was at the same time at a loss what expedient to substitute. The Justiciary of Arragon he observed became by degrees, the lawgiver.

_{- James Madison's Notes of Debates in the Federal Convention, August 15, 1787}

Note the language used here, however: ought. A rudimentary understanding of English would elucidate that, clearly, this meant that such a power for judges to set aside laws did indeed exist. That Mercer's misgivings were not shared by the rest of the Convention, however, is obvious - no motion to deny judges the power of judicial review was even tabled, let alone passed. Moreover - confessing that he had no better alternative than judicial review, Dickinson would voice support for the doctrine elsewhere.

Clearly, therefore, in vesting the Supreme Court with the "judicial power of the United States", the Constitution's framers understood said power to include judicial review.

Ratification of the Constitution

The campaign to ratify the Constitution (naturally) attempted to garner support by explaining the implications of the proposed document. In the process, they clearly demonstrated that contemporaries understood that by vesting the Supreme Court with judicial powers, that institution was also empowered to conduct judicial review.

The Federalist Papers, for instance, contained this elaboration on the judiciary.

[T]he courts were designed to be an intermediate body between the people and the legislature ... to keep the latter within the limits assigned to their authority. A Constitution is, in fact, and must be regarded by the Judges, as a fundamental law. It therefore belongs to them to ascertain its meaning, as well as the meaning of any particular Act proceeding from the Legislative body. If there should happen to be an irreconcilable variance between the two ... the Constitution ought to be preferred to the statute, the intention of the People to the intention of their agents.

Nor does this conclusion by any means suppose a superiority of the Judicial to the Legislative power. It only supposes that the power of the People is superior to both; and that where the will of the Legislature, declared in its statutes, stands in opposition to that of the People, declared in the Constitution, the Judges ought to be governed by the latter rather than the former.

_{- Federalist No.78 by Alexander Hamilton}

Alexander Hamilton was, of course, far from alone in this interpretation of the Constitution.

I say, under this Constitution, the legislature may be restrained, and kept within its prescribed bounds, by the interposition of the judicial department. ... it is possible that the legislature, when acting in that capacity, may transgress the bounds assigned to it ... but when it comes to be discussed before the judges, when they consider its principles, and find it to be incompatible with the superior power of the Constitution, it is their duty to pronounce it void; and judges independent, and not obliged to look to every session for a continuance of their salaries, will behave with intrepidity, and refuse to the act the sanction of judicial authority.

The honorable gentleman from Cumberland says that laws may be made inconsistent with the Constitution; and that therefore the powers given to the judges are dangerous. For my part, Mr. President, I think the contrary inference true. If a law should be made inconsistent with those powers vested by this instrument in Congress, the judges, as a consequence of their independence, and the particular powers of government being defined, will declare such law to be null and void; for the power of the Constitution predominates. Any thing, therefore, that shall be enacted by Congress contrary thereto, will not have the force of law.

_{- Speech of James Wilson in the Pennsylvania Ratifying Convention, December 7, 1787}

Moreover, even by those who opposed the new Constitution agreed with this interpretation. An article in Philadelphia's Chronicle of Freedom actually cites judicial review of legislation as a reason to be against the Constitution:

[T]here is a further barrier ... namely, the supreme court of the union, whose province it would be to determine the constitutionality of any law that may be controverted ... it would be their sworn duty to refuse their sanction to laws made in the face and contrary to the Letter and spirit of the constitution ... The 1st section of 3d article gives the supreme court cognizance of not only the laws, but of all cases arising under the constitution, which empowers this tribunal to decide upon the construction of the constitution itself in the last resort.

_{- Centinel XVI, Philadelphia Independent Gazetteer, Feb 26, 1788}

Thus, the Constitution was ratified with the understanding that the Supreme Court held the power of judicial review.

In conclusion, contrary to the dogmatic assertions of modern commentators voicing their political preferences, in 1778 Judicial review was so well established that it is simply assumed to exist. The lack of controversy surrounding it is evidence for how well it was accepted by contemporaries. Marshall's Supreme Court did not invent it in 1803.