  Let C be a smooth projective algebraic curve of genus g over the finite field
F_q. A classical result of H. Martens states that the Brill-Noether locus of
line bundles L in Pic^d C with deg L = d and h^0(L) >= i is of dimension at
most d-2i+2, under conditions that hold when such an L is both effective and
special. We show that the number of such L that are rational over F_q is
bounded above by K_g q^(d-2i+2), with an explicit constant K_g that grows
exponentially with g. Our proof uses the Weil estimates for function fields,
and is independent of Martens' theorem. We apply this bound to give a precise
lower bound of the form 1 - K'_g/q for the probability that a line bundle in
(Pic^(g+1) C)(F_q) is base point free. This gives an effective version over
finite fields of the usual statement that a general line bundle of degree g+1
is base point free. This is applicable to the author's work on fast Jacobian
group arithmetic for typical divisors on curves.
