First, I would use something like training in your query string. It's a little more readable and you aren't searching for the words lunge and dumbbell anywhere in those entries, just entries related to those category slugs.
{# First you would find any training categories in the URL query string. #}
{% set trainingQuery = craft.request.getParam('training') %}
{# Then find categories that match the slugs in your query string. #}
{% set trainingCategories = craft.categories.group('trainingCategoryGroup').slug(trainingQuery) %}
{# setup your search parameters #}
{% set searchParams = {
relatedTo: trainingCategories,
section: 'exercisesDb'
} %}
{# Find your entries #}
{% set entries = craft.entries(searchParams).order('score') %}
Your search form just needs to have the checkbox's input name as training[]. If it's on the same page, test to see if the category slug is in the trainingQuery array so it can be marked as checked or not.
Create this by finding all the categories in the trainingCategoryGroup group.
<form action="http://www.website.com/training/exercise-list">
{% for category in craft.categories.group('trainingCategoryGroup') %}
<label><input type="checkbox" name="training[]" value="{{ category.slug }}" {{ category.slug in trainingQuery ? 'checked'}}>{{ category.title }}</label><br>
{% endfor %}
<button type="submit">Search</button>
</form>
Then output your list of entries. This is a simple example.
{% if entries | length %}
<ol>
{% for entry in entries %}
<li>
<a href="{{ entry.url }}">{{ entry.title }}</a><br />
</li>
{% endfor %}
</ol>
{% else %}
<p>No results</p>
{% endif %}
If the query string is blank, this will show all of your entries. If you want to restrict that, you can wrap the previous code block in this...
{% if trainingQuery %}
... (entries) ...
{% endif %}
This is an inclusive search that will match entries in ANY selected categories. If you want an exclusive search instead (category AND category), you have to do it a little differently.
{# Get search parameters from the URL query string #}
{% set trainingQuery = craft.request.getParam('training') %}
{# Start an array of search parameters (relationParam) with 'and' to match ALL categories #}
{% set relationParam = ['and'] %}
{# Find categories that match the slugs in your query string... #}
{% for querySlug in trainingQuery %}
{% set trainingCategory = craft.categories.group('trainingCategoryGroup').slug(querySlug) %}
{# And merge them into the relationParam array. #}
{% set relationParam = relationParam|merge([{ targetElement: trainingCategory }]) %}
{% endfor %}
{# Avoid passing an array with `['and']` only #}
{% if relationParam|length < 2 %}
{% set relationParam = '' %}
{% endif %}
{% set searchParams = {
relatedTo: relationParam,
section: 'exercisesDb'
} %}
