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.