I am tacitly assuming that your curves should also be non-contractible, otherwise you have to add 1 to the answer. Let's suppose for simplicity that the surface is closed (but the argument adapts in a straightforward way to the non-closed situation) and has negative Euler characteristic.

Clearly, the best solution is to have your curves decompose the surface into pairs-of-pants (discs are forbidden; annuli are forbidden; and any other surface can be further decomposed).

Each pair-of-pants has Euler characteristic -1, and contributes 3/2 boundary curves (dividing by 2 to account for the fact that each boundary curve appears twice). The answer is then
-3/2 the Euler characteristic, as described in the first answer above.

pant decompositionof the surface. That there's $3g-3$ curves in such a decomposition is a very old result, observed probably by many people but certainly well-known by Poincare's time. Such curve collections are used to put "coordinates" on the collection of all curves on the surface, usually called "Dehn-Thurston coordinates". – Ryan Budney Apr 7 '12 at 10:06