I don't think there's any general algorithm that works for arbitrary semirings.  The requirement to be a semiring doesn't give us a lot to work with.

However, if you have a *closed* semiring, then there *are* algorithms for solving systems of linear equations over the semiring.

Closed semirings
================

A closed semiring is a semiring with a closure operator, denoted $*$, which satisfies the equation

$$a^* = 1 + a \times a^* = 1 + a^* \times a.$$

A closed semiring is also known as a [star semiring](https://en.wikipedia.org/wiki/Semiring#Star_semirings).

The intuition is that $a^*$ is intended to be the sum of the infinite series

$$1 + a + a^2 + a^3 + \dots$$

For instance, the regular languages form a closed semiring under union and concatenation; the $*$ operator is the Kleene star.  The real numbers form a closed semiring under addition and multiplication; the $*$ operator is $a^* = 1/(1-a)$.

Systems of linear equations over a closed semiring
==================================================

Now, if you have that kind of structure, then there *is* an analog of Gaussian elimination.  In particular, if you have a linear system of equations

$$Ax+b = x$$

where $x$ is a vector of variables over the closed semiring, $b$ is a vector of constants, and $A$ is a matrix of constants, then this has the solution

$$X = A^* B.$$

The closure operator on matrices takes a bit of work to define, but it can be computed efficiently using an analog of Gaussian elimination.

For a careful development of the theory, I recommend the following papers:

Stephen Dolan.  [Fun with Semirings: A functional pearl on the abuse of linear algebra](http://www.cl.cam.ac.uk/%7Esd601/papers/semirings.pdf).  International Conference on Functional Programming, ICFP '13.

Daniel J. Lehmann.  [Algebraic structures for transitive closure](http://www.sciencedirect.com/science/article/pii/0304397577900561/pdf?md5=54d77d786ce7532bbd9d93d61b5886e6&pid=1-s2.0-0304397577900561-main.pdf).  Theoretical Computer Science, vol 4 pp.59--76, 1977.