How to state that a complexity bound does not depend on a given parameter size? I am often ill at ease with Landau (Big O) notation, because it seems
often to be abusing mathematical notation. The best example is the use
of the equal sign to express a set membership. And this can be
misleading.

I have an algorithm that is dependent on two parameters $n$ and $m$,
which are the respective sizes of the two pieces of data it works on,
like (for example) in the case of a substring search, where you have
the size $n$ of the string being searched and the size $m$ of the
pattern to be found.

I want to express that the algorithm is $O(n)$, but with a constant
that is independent of the value of $m$.

A simple example is the recognition of a regular set, which is linear
in the size of the input string, independently of the size of the
regular expression defining the regular set, provided it has been
compiled into a DFA (which is supposed to be amortized on many
recognitions). This is usually implicit, but can I make it explicit when it is less obvious, or less well known.

The problem seems to be that people will often write $f(n)\in O(g(n))$
to mean that ultimately $|f(n)|\leq k\cdot |g(n)|$ even when $k$
actually depends on $m$. I realize that this depends on how you look
at the problem, and whether you consider that the parameter of size
$m$ is part of the data.

But then, how can one state unambiguously and clearly, but without
being too verbose, that, though the size $m$ parameter is part of the
data, the algorithm is $O(g(n))$ independently of $m$, i.e. the same
constant $k$ can be used even though $m$ may grow arbitrarily? Is there a notation or terminology for it?

Is there a better way recommended by HABON (the High Authority on Big
O Notation)?
The usual convention is to state upfront that your big O notations are with respect to $n$, and that whenever the constant depends on some parameter $m$, then you write $O_m(\cdot)$.

If in another paper you are fine with allowing the constant to also depend on the parameter $m$, then instead you state upfront that your big O notations are with respect to $n$, and the underlying constant could depend on $m$. Then you can use Luke Matheison's suggestions that if in some case your big O doesn't depend on $m$, then you mention that in that case the underlying constant doesn't depend on $m$; but that could be more confusing than the convention in the preceding paragraph.