Off-road navigation in challenging terrains, such as planetary surfaces, military zones, and Search and Rescue (SAR) missions, demands autonomous solutions to replace human involvement. Uncrewed Ground Vehicles (UGVs) play a pivotal role in executing tedious, cognitively demanding, and hazardous tasks. Central to these autonomous systems is trajectory planning, vital for efficient and secure navigation through complex, dynamic environments. Our survey starts with an outline of the state-of-the-art of trajectory planning algorithms specific for off-road applications, ranging from heuristic methods to learning-based approaches, and emphasizing their application, challenges, and constraints. We delve into real-time planning, scalability, robustness, adaptability, and handling uncertainties. Furthermore, we investigate the integration of mission-specific goals like threat avoidance, energy efficiency, and time-critical operations into trajectory planning; in addiction, the survey also explores methods to incorporate these factors into the algorithmic framework, highlighting recent advancements and potential research directions. Finally, we provide a synthesis of the main findings with the goal to inform algorithm selection amidst the myriad of possibilities and lead toward a structured approach for specific contexts.