Implementation of arbitrary-precision integer addition
How can I improve this implementation?  


You could extract the string parsing to a separate int[] ToIntArray(String) method.
You could add a separate int[] Add(int[],int[]) method.
You could add a separate String ToString(int[]) method.  

Right now your method is 


parsing the String's to int[]
adding two int[]
composing a string out of the adding  


So after extracting the methods your former Add() method would look like  

string Add(string a,string b)
{
    int maxLen = Math.Max(a.Length,b.Length);
    a = a.PadLeft(maxLen+1,'0');
    b = b.PadLeft(maxLen+1,'0');

    int[] arr1 = ToIntArray(a);
    int[] arr2 = ToIntArray(b);

    int[] sum = Add(arr1,arr2);

    return ToString(sum);
}  


But wait, we can do much better using more OOP.  

Let us introduce a new class IntArray ( which can be private ). In this class we override the ToString() method, add constructors for int[] and string and also add a + operator.  

private class IntArray
{

    public int[] array { get; private set; }
    public IntArray(int[] arr)
    {
        array = arr;
    }

    public IntArray(String s)
    {
        array = s.Select(x =&gt; int.Parse(x.ToString())).ToArray();
    }

    public static IntArray operator +(IntArray summand1, IntArray summand2)
    {
        int[] sum = new int[summand1.array.Length];
        int carry = 0;

        for (int i = sum.Length - 1; i &gt;= 0; i--)
        {
            int total = summand1.array[i] + summand2.array[i] + carry;
            sum[i] = total % 10;
            if (total &gt; 9) 
            {
                 carry = 1;
            }
            else 
            {
                carry = 0;
            }
        }

        return new IntArray(sum);
    }
    public override string ToString()
    {
        return string.Concat(array.SkipWhile(x =&gt; x == 0));
    }

}  


This will simplify your former Add() method to  

string Add(string a, string b)
{
    int maxLen = Math.Max(a.Length, b.Length);
    a = a.PadLeft(maxLen + 1, '0');
    b = b.PadLeft(maxLen + 1, '0');

    IntArray arr1 = new IntArray(a);
    IntArray arr2 = new IntArray(b);

    return (arr1 + arr2).ToString();
}


Update: Based on d347hm4n's comment and after checking the reference source, I changed to implementation of ToString() from String.Join() to String.Concat() method.