First of all, I found this link which was a HUGE help to get this working.
But wanted to post my findings - in case it helps anyone else.
Step 1: Add a Service Reference to your project (WCF Web Service)
Step 2: Create NetSuitePortTypeClient and Open it (use your own account specific)
NetSuitePortTypeClient nsptc = new NetSuitePortTypeClient(NetSuitePortTypeClient.EndpointConfiguration.NetSuitePort, "https://########.suitetalk.api.netsuite.com/services/NetSuitePort_2021_2");
await nsptc.OpenAsync();
Step 3: Create a Transaction Search in this example
        TransactionSearch tranSearch = new TransactionSearch();
        TransactionSearchBasic tranSearchBasic = new TransactionSearchBasic();
        SearchStringField searchstringfield = new SearchStringField();
        searchstringfield.@operator = SearchStringFieldOperator.@is;
        searchstringfield.operatorSpecified = true;
        searchstringfield.searchValue = "$$$$$$";
        tranSearchBasic.tranId = searchstringfield;
        tranSearch.basic = tranSearchBasic;
Step 4: Call the Search
searchResponse sresponse = await nsptc.searchAsync(CreateTokenPassport(), null, null, null, tranSearch);
AND Here is the CreateTokenPassword function
    public TokenPassport CreateTokenPassport()
    {
        string account = "account";
        string consumerKey = "ckey";
        string consumerSecret = "csecret";
        string tokenId = "token";
        string tokenSecret = "tokensecret";
        string nonce = ComputeNonce();
        long timestamp = ComputeTimestamp();
        TokenPassportSignature signature = ComputeSignature(account, consumerKey, consumerSecret, tokenId, tokenSecret, nonce, timestamp);
        TokenPassport tokenPassport = new TokenPassport();
        tokenPassport.account = account;
        tokenPassport.consumerKey = consumerKey;
        tokenPassport.token = tokenId;
        tokenPassport.nonce = nonce;
        tokenPassport.timestamp = timestamp;
        tokenPassport.signature = signature;
        return tokenPassport;
    }
 
     
    