How to connect this 7 segment LED display to Arduino?
The clock and data pins are for your serial input. These can be controlled directly from the Arduino, just connect each to a digital out.  

For the data routine, according to the datasheet there is one start bit, followed by 35 data bits which correspond to the "Serial Input Sequence" table in your question.

Create a function in your "sketch" to control the serial loading, something like below - I haven't checked this code. You only need to call it whenever you want to update the display.
You will have to replace the set_data_pin and set_clock_pin with the correct Arduino calls to whatever GPIO pins you have attached to the clock data pins on the display (I don't use Arduino so I don't know them) Same for the delay_us (microsecond delay) which can be adjusted to whatever timing you want up to 500kHz clock speed - you can add a define for the value to save changing each one.
Each segment is shifted out MSB to LSB, which corresponds with A(MSB) to DP(LSB) for each input char: 

void load_data(char seg1, char seg2, char seg3)
{
    char i, temp;
    char position = 0;

    set_data_pin(1);  // clock start bit in
    set_clock_pin(1);
    delay_us(5);
    set_clock_pin(0);
    delay_us(5);

    temp = seg1;
    while(i&lt;8)
    {
        set_data_pin(temp &amp; 0x80);  // set data pin
        set_clock_pin(1);
        delay_us(5);
        set_clock_pin(0);
        delay_us(5);
        i++;
        temp = temp &lt;&lt; i; // shift next bit out
    }

    temp = seg2;
    while(i&lt;8)
    {
        set_data_pin(temp &amp; 0x80);  // set data pin
        set_clock_pin(1);
        delay_us(5);
        set_clock_pin(0);
        delay_us(5);
        i++;
        temp = temp &lt;&lt; i; // shift next bit out
    }

    temp = seg3;
    while(i&lt;8)
    {
        set_data_pin(temp &amp; 0x80);  // set data pin
        set_clock_pin(1);
        delay_us(5);
        set_clock_pin(0);
        delay_us(5);
        i++;
        temp = temp &lt;&lt; i; // shift next bit out
    }

    // Last 11 bits - do something here if needed
    while(i&lt;11)
    {
        set_data_pin(0);  // set data pin
        set_clock_pin(1);
        delay_us(5);
        set_clock_pin(0);
        delay_us(5);
        i++;
    }
}


Connections


Connect the VDD pin to +5V, and the VSS pin to ground (0V) 
Connect the VLED pins to +5V also. 
Connect the DATA ENABLE pin low (i.e. to ground), as it is active low. 
For Bits 25-34 pins, leave these unconnected if you don't wish to use them, otherwise you can use them as digital outputs. Don't tie them high or low (i.e. don't connect to +5V or ground)  
For the BC (brightness control) pin, you can use just a resistor to fix the brightness, or a potentiometer and resistor to control the brightness of the display.
To work out the value we can use the info in the datasheet: 


The absolute maximum \$I_f\$ (forward current) for the display is 30mA (pg.2)
The display current is typically 36 times larger than the current into the BC pin (pg. 4) and the maximum current into the BC pin is \$550\mu A\$ (pg.5)


So with this info we can work out the best value for the pot. If we aim for a typical operating maximum of 20mA, then:  

\$  \dfrac{+5V}{20mA \div 36} = 9k\Omega \$   

This is the minimum value of resistance we would use (connected between +5V and BC pin)
If we want to vary the current, say from \$10mA - 20mA\$, then we can add a \$9k\Omega\$ pot in series with the resistor with it's wiper connected to one end (either end) Then the current varies between:

\$ \dfrac{+5V}{9k\Omega} \times 36 = 20mA \$  

with the pot turned fully the other way  

\$ \dfrac{+5V}{9k\Omega + 9k\Omega} \times 36 = 10mA \$

Note that the datasheet is not particularly helpful with details on the brightness control pin - it shows the pot set up for a varying voltage control in the diagram which confuses things a bit. I have just ignored this diagram and taken what is written to be correct. I'm also assuming the resistance to be across the full 5V (i.e. the BC pin is just above 0V), which is probably not be the case, but it's better to be on the conservative side if no details are given.
This means you may need to experiment a bit to get the brightness right - if it's too dim try changing to a lower resistance.