The problem here isn't an issue with Linux redirection; rather, it's a fundamental misunderstanding of how the pipeline works. Redirection here isn't working because only cut is actually printing to stdout. stdout for the echo command has been piped to cut's stdin (which isn't being used in this case since a file is specified).
echo "header line" > output_file && cut -c 1-5 input_file >> output_file
is what you want, and not inelegant at all (I replaced your
&& so that the cut command will only execute if the header is successfully written; this way it won't execute if you don't have permissions to create or write to output_file).
You could also do it all in a subshell, eg.
(echo "header line"; cut -c 1-5 input_file) > output_file
but there's no real benefit to doing this and with more complex examples it can cause issues if you're not familiar with how the subshell is scoped.
If you want cut to pass stdin through to stdout you could try:
echo "header line" | cut -c 1-5 - input_file
(The dash is a common shortcut for stdin)
However, this will also perform the cut operation on stdin (resulting in a header line of "header"). It's hard to tell if this is what you want or not from the question.