As with many of its powers, congress did not actually vote on and grant letters of marque and reprisal in individual cases. Rather, it passed laws delegating that power to the executive. It is not very difficult to find images of such letters from the war of 1812, and they are all issued by the president "in pursuance of an act of congress," not directly by congress itself, and signed by both the president and the secretary of state.
To address the question more generally, congress exercises its enumerated powers by passing laws -- also known as acts of congress -- and these must be enacted through the process provided in section 7 of article 1, generally requiring the president's signature or a 2/3 vote by both houses to override a veto. Lest anyone argue that this process applies only to measures that are explicitly called "bills" and destined to become "laws" (for those are the terms used in the text), the drafters of the constitution closed section 7 with this paragraph:
Every Order, Resolution, or Vote to which the Concurrence of the Senate and House of Representatives may be necessary (except on a question of Adjournment) shall be presented to the President of the United States; and before the Same shall take Effect, shall be approved by him, or being disapproved by him, shall be repassed by two thirds of the Senate and House of Representatives, according to the Rules and Limitations prescribed in the Case of a Bill.
Privateering and the letters of marque and reprisal that authorize it are generally repudiated in international law, so it is unlikely that the US would actually exercise the power today, but theoretically, if it did, congress could pass a law vesting the power to sign these letters in a cabinet officer rather than with the president, or perhaps authorizing the president to delegate it to them, or what have you. Or, if it was to be done rarely and was seen as a particularly delicate matter (as it would in fact be), congress could retain its right to act in individual cases. Under section seven, however, this would nonetheless, as the question asks, require the president's signature or a veto override.
(An interesting question might be, if congress were to vote to exercise its power to grant a letter of marque to, say, Someone against the president's wishes, and then overrode the president's veto, what form would the letter take? Congress isn't generally supposed to have executive function. Who would sign the letter? Would it have to come with a certificate from the clerk of the house and the secretary of the senate certifying that it was duly authorized? Or would such a vote be impossible to execute unless the president bowed to the threat of impeachment?)