When you build any board game, its generally better to keep separate classes for organization ,search,evaluation.
I suggest you to write a clean 2-player game.
Then make the AI component by allowing it to play random. This will test for legal moves in a position and winning combinations.
in connect four, winning is simple, so make another fuction, let it return some value if any player has won, this is your maximum score, and in game like connect4, this is what we want to achieve.
Then make sure you would add in more sophisticated search algorithm like min-max. Here I would like to suggest you that you go for a better frame-work of min-max namely "nega-max".
Once you get this working, then add in alpha-beta pruning , PVS or what ever you feel like.
Answer for your 1) ::
Computer in normal min-max search will compare all the scores
say best_move has score +5 and move B will have score +7 then best_move's score will be assigned as 7 and best_move now will be move B.
However, addition of alpha-beta changes the things quickly.
By adding alpha-beta, search doesnt evaluate all nodes(moves), thus it is faster than naive min-max.
Answer for your 2) ::
It differs from programer to programer. In general and widely used basic data-structure are arrays.
Arrays is java are certainly faster than Strings.
If you think further, assuming your game is for 7x6(standard board), there are only 42 cells.
long type in java offers uptil 64 bits, here you can allot 1-bit per cell so that takes only 42 bits.
This is a complicated approach but would be very fast. However I suggest you not to take this approach on first go, make a working connect4, then optimize it.
I hope this is not home-work.
If you want me to help you, then let me know so that I can write on it.