A fairly simple-minded approach would be to use a regular expression. Depending on which type of phone numbers you're accepting, you could write a regular expression that looks for the digits (for US-only, you know there can be 7 or 10 total - maybe with a leading '1') and potential separators between them (period, dash, parens, spaces, etc.).
Once you run the match against the regex, you'll need to write the logic to determine what you actually got and format it from there.
EDIT: Just wanted to add a very basic example (by no means is this going to work for all of the examples you posted above). Geoff's suggestion of stripping non-numeric characters might help out a bit depending on how you write your regex.
Regex regex = new Regex(@"(?<areaCode>([\d]{3}))?[\s.-]?(?<leadingThree>([\d]{3}))[\s.-]?(?<lastFour>([\d]{4}))[x]?(?<extension>[\d]{1,})?");
string phoneNumber = "701 123-4567x324";
Match phoneNumberMatch = regex.Match(phoneNumber);
if(phoneNumberMatch.Success)
{
if (phoneNumberMatch.Groups["areaCode"].Success)
{
Console.WriteLine(phoneNumberMatch.Groups["areaCode"].Value);
}
if (phoneNumberMatch.Groups["leadingThree"].Success)
{
Console.WriteLine(phoneNumberMatch.Groups["leadingThree"].Value);
}
if (phoneNumberMatch.Groups["lastFour"].Success)
{
Console.WriteLine(phoneNumberMatch.Groups["lastFour"].Value);
}
if (phoneNumberMatch.Groups["extension"].Success)
{
Console.WriteLine(phoneNumberMatch.Groups["extension"].Value);
}
}