Noether's Theorem: There are conserved quantities corresponding to symmetries of position, orientation, and time, but why not velocity? Noether's Theorem seems to be one of the most fundamental and beautiful results in all of physics. As I understand it, the fact that the laws of physics are the same independent of position, orientation, and time, leads to the conservation of momentum, angular momentum, and energy, respectively.  
But the laws of physics are also independent of velocity.  Why does this not lead to another conserved quantity?  Or is it just Newton's third law (forces in a closed system must add to zero)?
 A: The issue here is that the statement about laws of physics being independent of velocity has been misunderstood or is not precise enough. Noether's theorem pertains explicitly, theories described through a Lagrangian. A Lagrangian in its bare bones, should contain a kinetic term of some sort. Without going to a relativistic setting, you can consider a free particle in classical mechanics, for which
$$L_{\rm free} = \frac{1}{2} m \left(\frac{dx}{dt}\right)^2 = \frac{1}{2}m v^2$$
You can easily try to displace the speed $v\rightarrow v + \Delta v$, and you will see that the Lagrangian actually changes by an amount which should be proportional to acceleration, therefore a system described by such Lagrangian is not invariant under infinitesimal changes in velocity in general. Since this term (or similar) appears in most Lagrangians of physical systems, changes in speed do not correspond to symmetries.
This however does not mean that one cannot build a Lagrangian which is indeed symmetric under such changes. As it has been mentioned in the comments and other answers, if you interpret displacements in speed, as "boosts", then a relativistic Lagrangian does display such symmetry, although it is often more useful to think about it as an imaginary rotation, rather than a shift in velocity (if it is understood in a linear way), or in other words one is changing time and space in a very specific way, see Lorentz transformations.
I would suggest to try to follow the usual derivation of conserved currents to see the Lagrangians do not generally display a "speed" symmetry at least not in the Noether sense of symmetries. I also recommend considering the action associated to the Lagrangian above with the addition of a square root, which makes the action "speed invariant" because it will only depend on the end-points. This illustrates clearly the point that kinetic energy is frame-dependent (in classical mechanics), but the actual arc-length of the trajectory is not.
A: There are conserved quantities related to Lorentz boosts. These are included in the angular momentum tensor, which is conserved if the Lagrangian is invariant under Lorentz transformations.
