Searching for entries across multiple fields including a relationship
I think I just had my Craft "Lightbulb moment".

I've got this working now. Once I realised that I needed to retrieve the category as an object in order to match against it using relatedTo it made more sense.

I also realised that I needed to used a wildcard rather than an empty string if a parameter was missing.

Here's my solution:

{% set cat = craft.request.getParam('category') ? craft.request.getParam('category') : '' %}
{% set start_date = craft.request.getParam('start_date') ? craft.request.getParam('start_date') : 0 %}
{% set wage_from = craft.request.getParam('wage_from') ? craft.request.getParam('wage_from') : 0 %}
{% set wage_to = craft.request.getParam('wage_to') ? craft.request.getParam('wage_to') : 9999 %}
{% set location = craft.request.getParam('location') ? craft.request.getParam('location') : '*' %}

{%
  set category = craft.entries({
        section: 'apprenticeshipsCats',
        title: cat
  })
%}

{%
  set results = craft.entries({
      section: 'vacancies',
      relatedTo: category,
      location: [
            'and',
            '= ' ~ location
        ],
        wage: [
          'and',
          '&gt;= ' ~ wage_from,
          '&lt;= ' ~ wage_to,
        ],
        startDate: [
          'and',
          '&gt;= ' ~ start_date
        ]
    })

%}


So I still fetch the parameters and set default values for them, note the wildcard if "Location" is empty.

But then I get the category to be searched as a craft entries object.
Once I have that I can use its reference in my results query and bingo!