Lawyer here with a background in constitutional history and federalism. The answer largely requires understanding the purpose of the Constitution. At the time it was drafted, there was little concept of a nation of “Americans.” There was a nation of North Carolina, a nation of Massachusetts, a nation of New York, etc. The constitutional convention was an effort to find ways these many small nations could work together to strengthen each other. This required giving up some of their sovereignty to a new federal government. But they were very skeptical of doing so, and states wanted to retain as much sovereignty as possible.

Therefore, the approach was not to create a federal government with broad powers, but rather to only assign it specific and limited powers—namely, those powers that the states couldn’t really handle themselves. That’s why the Constitution specifically gives the federal government power over things like interstate commerce and foreign diplomacy. These are things that require some syncing up and that one state simply cannot deal with on its own.

But here’s the key point: Any power not specifically assigned by the Constitution to the federal government remained (and still remains) with the states. So if there was anything at all—no matter how big or small—that needed to be handled by the federal government, it had to be specifically mentioned in the Constitution.

With respect to the Post Office, you can start to see how the mentality of early Americans on this point would naturally lead to it being included in the Constitution. Each state’s leaders would have seen mail services as something that any one state can’t really deal with on its own. Why have 13 different mail systems with different standards, when that power could just be assigned to the federal government and be much more efficient? So they decided to assign it to the federal government. And given the constitutional setup—all power with the states except what we have specifically designated as belonging to the feds—it therefore had to be listed in the Constitution by name.

This answer to some extent overlaps the nice answer already provided (while I was writing this one), but there's a few additional details here, so I thought I'd provide it anyway.

There are two important pieces of context necessary to understand how the power to "establish Post Offices and Post Roads" (called the "Postal Clause") landed in the Constitution.

The first thing to understand is that the Articles of Confederation (the interstate compact that preceded the United States Constitution) provided the federal Congress with the power to establish and regulate Post Offices. So one immediate reason that the Constitution provided a Postal power to the federal Government was that it was already a power being exercised by the federal government going into the Constitutional Convention. At least some of the founders were not pleased with Postal administration under the Articles, however. For example, in a letter from John Jay to George Washington in 1789, Jay notes:

The Direction of the Post Office, instead of being as hitherto, consigned chiefly to a committee, and managed without much System, should I think be regulated by Law, and put under the Superintendence, and in some Degree under the controul of the Executive. The Public are not well satisfied on this Head, as Matters now stand, and there is but little Reason to expect any important change during the Existence of the present Government. The succeeding one will have an opportunity of doing a very acceptable Service to their Constituents by regulating the Post office in a proper Manner; and the more of such things they may have to do, the better.

The Articles of Confederation provided only a power relating to Post Offices, but, during the Constitutional Convention, the founders discussed adding several additional related powers to the Constitution, such as adding a power to establish "post roads," a power to "cut canals" (proposed by Benjamin Franklin), or a power to "to grant charters of incorporation where the interest of the U.S. might require the legislative provisions of individual States may be incompetent" (proposed by James Madison). Of the debated powers, the only additional power that was actually incorporated into the Constitution, however, was the power to establish "Post Roads." More significant changes to the postal organization would have to await the First Congress's enactment of the Act of September 22, 1789 and the Postal Service Act of 1792. But that's only a very narrow answer to your question.

The second and broader answer is that the founders conceived of the federal government as a government of limited powers. This scheme is made explicit by the 10th amendment which provides that "[t]he powers not delegated to the United States by the Constitution, nor prohibited by it to the States, are reserved to the States respectively, or to the people." That is to say, the United States Congress (and the federal government more generally) only has the powers given to it by the Constitution, and no others. The Constitution contains an extensive list of so-called "enumerated powers" for the Congress, which includes the power to establish Post Offices and Post Roads, but also includes, for example, a power to "regulate Commerce with foreign Nations, and among the several States, and with the Indian Tribes", and to "coin Money, regulate the Value thereof, and of foreign Coin, and fix the Standard of Weights and Measures." You may see a theme here, which is that many of the powers the Constitution provides to Congress relate to areas which necessarily affect the interest of the States collectively and that may not be adequately addressed by states acting individually.

So the ability of the Congress to establish Post Offices and Post Roads can be understood as another way in which the founders sought to provide the nascent federal government with a clearly enumerated ability to regulate and address areas that affected the interests of multiple states, which the delivery of mail unquestionably does. For example, in the Records of the Federal Convention, during a discussion of whether to add additional powers to the clause, James Madison noted that the primary object of the clause, in his view, was to "secure an easy communication between the States." In short, because the mail, by its nature, must travel between the states, the founders viewed it as a function better regulated by the federal government.

Sources:

Library of Congress, The United States Constitution Annotated (2013)

Farrand, Records of the Federal Convention of 1787, Vol.2

The Founders' Constitution Volume 3, Article 1, Section 8, Clause 7 (relevant materials available at https://press-pubs.uchicago.edu/founders/tocs/a1_8_7.html)

Richard R. John's Spreading the News: The American Postal System from Franklin to Morse is generally seen as the authoritative history of the early postal service, so that's a great place to look for more information. The following information is based on his book.

John emphasizes the importance of newspapers to understanding why political leaders of the early republic cared about the postal service. Since there was no telegraph or technological equivalent in the late eighteenth century, news literally needed to be physically transported from place to place. As the Founding Fathers generally believed that an enlightened citizenship was important for a functioning republic, creating a well-functioning postal service was seen as important for moving newspapers between parts of the country and thus keeping the citizenry well-informed of events both near and far. Essentially, the post office was seen as important for preventing information from remaining too local in scope.

A seminal piece of legislation in this is the Post Office Act of 1792. In various ways, it admitted newspapers into the mail on unusually favourable terms. Prior to 1792, newspapers had not been formally carried via the postal system (though some postriders did so of their own accord). They were not only added in 1792, but made particularly cheap to ship. Newspaper mailing was thus essentially subsidized, constituting a lot of the weight of mail while only bringing in a small percentage of revenue. The Act also allowed newspaper printers to use the postal service to exchange papers with each other for free. This was important because it facilitated the reprinting of news from farther away in local papers.

John argues that in this early period (from 1792 to the end of the 1820s/mid-1830s), the postal service thus came to facilitate a national community of people sharing a particular public sphere of news. Ironically, he argues that this trend reversed at the end of this period, at which time the postal service facilitated sectional discord between North and South over slavery (I can elaborate on this if desired).

Late to the party, but...

What became The United States Postal Service had its first Postmaster General appointed July 26, 1775, nearly a full year before the Lee Resolution would prompt our Declaration of Independence and over a decade before the calls to amend the Articles of Confederation were answered. In November of the same year Congress resolved;

That all letters to and from the delegates of the United Colonies, during the sessions of Congress, pass, and be carried free of postage, the members having engaged upon their honour not to frank or enclose any letters but their own.

The post was a "federal authority" well before we even had a federal government, let alone a Constitution. Lets look at where that importance came from.

The first American Postmaster General was none other than Dr. Benjamin Franklin. He had been colonial postmaster until stripped of that title in late January of 1774, only a day after taking a tongue lashing from Alexander Wedderburn of the Privy Council in the cockpit, namely for the Boston unrest and Hutchison Affair. He had gained the positon in 1753 after the death of Elliot Benger who had held the position prior. Franklin was qualified as postmaster of Philadelphia, a position he accepted in 1737 after a strange battle of sorts with a man named Andrew Bradford who held it previously.

Now going forward in time... Ben Franklin became Post Master of Philadelphia (again, in 1737) only a few years after acquiring the Pennsylvania Gazette (in 1729, at the young age of 23) and offered to deliver the paper by postal rider to subscribers. At that point it became the most circulated paper in British North America and increased not only sales but advertising revenue as well. By 1748 Franklin was able to officially retire from printing, but soon after was made Postmaster for the Colonies. In 1752 he printed his kite experiment and in 1754 created what some believe was the first political cartoon, [join or die] (https://upload.wikimedia.org/wikipedia/commons/thumb/9/9c/Benjamin_Franklin_-Join_or_Die.jpg/300px-Benjamin_Franklin-_Join_or_Die.jpg). Once Colonial Postmaster, he surveyed over 1500 miles of road and even attached an odometer to a wheel that counted each revolution made to determine the best and fastest routes. It was with this information postal rates were determined, also factoring in package weight. This became critically important to the rapid spread of news and ideas in the 1760s and 1770s as the Revolution approached.

The importance of news traveling by papers to communities cannot be properly conveyed today. It was telephone, t.v., internet, social media, etc all wrapped into one and if you could read, you needed the paper. It was the source of all information. But how did the info get printed?

If the printer was also the post master, his paper would have all the news before any other in town because news traveled by post (which is the real answer to your question). Franklin, having Philly's 2nd newspaper, was a very smart man that figured this out early on. Unfortunately for him he learned it from that previous Philadelphia Postmaster and founder of the The American Weekly Mercury, Philadelphia's first newspaper, Andrew Bradford. Bradford had already been offering postal delivery of his Mercury but forbid any of his riders from delivering the Gazette which angered Franklin. After a few years of back and forth jabs, Bradford became engrossed in the contest and allowed his account management to become unsatisfactory. As a result his resignation was demanded by the post master for the Colonies and the job was instead offered to Franklin. He later said of the position;

Though the salary was small, it facilitated the correspondence that improved my newspaper, increased the number demanded, as well as the advertisements to be inserted, so that it came to afford me a very considerable income.

So in 1737 we had a postmaster for all colonies. Where did that start? With John Hamilton in 1707 after the British government purchased the rights from the estate of the Gov of NJ, Andrew Hamilton, who had started a colonial postal service in 1692 after acquiring the grant to do so from a man named Thomas Neale, who never visited North America. In many cases Hamilton just connected existing routes. Philadelphia had a post office since 1683 when it was started by William Penn himself. In 1673 the Gov of NY eatablished a route between NY and Boston, with Massachusetts starting their mail service in 1633 - only a handful of years after founding the colony.

By 1792, a full 100 years after the first full colonial postal service was established by William and Mary through Gov Hamilton, a very large portion of literate Americans had recieved the vast majority of news namely by papers through postal delivery their whole lives, making them not only a vital source of news but also making the postal service vital to its distribution among them.

More can be said on it being a federal authority and its later legislation, as others have, but it all comes back to two points: 1) News comes in the mail and 2) it always has in America.