Achieving decarbonization in the shipping sector poses distinct challenges because of this sector's hard-to-abate nature, such as international dimension, technical demands, reliance on energy-dense fuels, and complex stakeholder ecosystem. Despite some literature addressing many of these challenges, they are often limited to a purely techno-economic perspective. The present research addresses the shipping sector decarbonization by developing a comprehensive Energy System Optimization Model TIMES-ShEU, tailored to analyze cost-effective pathways for reducing greenhouse gas emissions in the shipping sector at the European Union (EU) level. The study evaluates the role of alternative energy carriers, such as biofuels and electrofuels (e-fuels), under different modeling scenarios that represent current and future EU climate and shipping-related policy. The modeling exercise is further complemented with a cross-sectoral perspective, but also an assessment of bioenergy sustainability criteria, including the availability of different types of biomass feedstock as well as the possibility (or not) of bioenergy imports. Overall, results indicate ammonia, as an e-fuel, to be a long-term solution due to its scalability and carbonless content, aligning thus, with 2050 net-zero targets. Nonetheless, when testing more ambitious regulatory and market-based policies, methanol, as a biofuel, is favored as a transition marine alternative energy carrier, mainly due to its relatively simple engineering. Furthermore, this study advocates that as stricter emission reduction policies and biomass availability constraints exert greater pressure on the system, the total system cost rises proportionally. Thus, these findings underscore the (i) role of policy in shaping the decarbonization of the EU shipping sector; and (ii) a cross-sectoral approach is necessary, in order to assess the shipping transition effectively,  while also taking into account the decarbonization of other energy sectors.