This question got some great, highly voted answers!
Ryan Cook's answer is close to what I'm after and may be more appropriate for other developers. However, it adds http:// to the beginning of the string and in general it does a bit more formatting than I'm after.  
Also, for my use cases, resolving relative paths is not important. 
mdsharp's answer also contains the seed of a good idea, although that actual implementation needed a few more details to be complete. This is an attempt to flesh it out (and I'm using this in production):
Public Function UrlCombine(ByVal url1 As String, ByVal url2 As String) As String
    If url1.Length = 0 Then
        Return url2
    End If
    If url2.Length = 0 Then
        Return url1
    End If
    url1 = url1.TrimEnd("/\")
    url2 = url2.TrimStart("/\")
    Return String.Format("{0}/{1}", url1, url2)
End Function
This code passes the following test:
<TestMethod()> Public Sub UrlCombineTest()
    Dim target As StringHelpers = New StringHelpers()
    Assert.IsTrue(target.UrlCombine("test1", "test2") = "test1/test2")
    Assert.IsTrue(target.UrlCombine("test1/", "test2") = "test1/test2")
    Assert.IsTrue(target.UrlCombine("test1", "/test2") = "test1/test2")
    Assert.IsTrue(target.UrlCombine("test1/", "/test2") = "test1/test2")
    Assert.IsTrue(target.UrlCombine("/test1/", "/test2/") = "/test1/test2/")
    Assert.IsTrue(target.UrlCombine("", "/test2/") = "/test2/")
    Assert.IsTrue(target.UrlCombine("/test1/", "") = "/test1/")
End Sub